我们将使用图表和两个玩家。在这个连接图中,获胜条件是第二个玩家没有其他路径可以采取。问题在于,一旦玩家采取了一条路径,就无法再次进行。
让我们假设初始输入是邻接列表(x,y)意味着x具有到y的路径
目标是返回玩家1可以选择的一组顶点,使其始终获胜。
例如,如果我有[(1,2), (2,0), (0, 3), (3,2)]
并且玩家1开始,那么我们应该返回[1, 0, 3]
。我们不能返回2
:
2 - >玩家1从这里开始
(2,0) - >选手2进入0
(0,3) - >玩家1进入3
(3,2) - >玩家2进入2
(2,0) - >球员1不能到这里,已经被带走了
already_visited = []
turn = 1
result = []
def findStarting(L):
global already_visited
global turn
global result
for x,y in L:
allowed = can_visit(L, y) # function tell me which I can visit safely
turn = (turn % 2) + 1 # increment the turn
already_visited.append((x,y)) # we visited this edge
res = findStarting([(x, y)]) # recursive call (search on this node for paths)
if (turn == 2): return True
def can_visit(L, y):
res = []
for a,b in L: if (a==y and (a,b) not in already_visited): res.append((a,b))
return res
我遇到了递归案件的问题。我想我要做的就是返回True
,如果我们达到转弯为2且玩家没有可以走的路径,但我不知道如何从这里前进
这是一个简单的递归解决方案。它没有效率,它是强力搜索而没有任何中间状态的缓存,所以它肯定可以更快,虽然我不知道是否有一个有效的(即非指数)解决这个问题。
def firstPlayerWins(g,v):
for i,e in enumerate(g):
if e[0]==v and not firstPlayerWins(g[:i]+g[i+1:],e[1]):
return True
return False
def winningVertices(g):
return [v for v in set(e[0] for e in g) if firstPlayerWins(g,v)]
winningVertices([(1,2), (2,0), (0, 3), (3,2)])
## [0, 2, 3]