我已经做了一段时间了,这是我到目前为止得到的。。。这个代码不起作用。此代码仅供参考。任务是一个没有围墙的迷宫。我必须使用递归算法。每个空间都有一个数字,当我降落在一个空间上时,这个数字告诉我在一个特定的方向上可以移动多少。我必须返回路径。(我已经做了一个版本,如果有解决方案,我会返回True或False。)我似乎无法返回路径本身。你知道吗
def pathsolve(self, start, end, vis=None):
z=self.__getitem__(start)
x,y=start
b=False
if path==None:
path=deque()
if vis==None:
vis=deque()
if start == end:
vis.appendleft(start)
return True
elif start in path:
return False
elif z==0:
return False
else:
#visited.add(start)
path.append(start)
if self.onboard((x+z,y)) and (x+z,y) not in path:
#print("going to"+str((x+z,y))+" by "+str(z)+" from "+str (start))
b=self.pathsolve((x+z,y),end, path)
#print()
if self.onboard((x,y+z)) and (x,y+z) not in path and b == False:
#print("xgoing to"+str((x,y+z))+" by "+str(z)+" from "+str(start))
b=self.pathsolve((x,y+z),end, path)
#print()
if self.onboard((x,y-z)) and (x,y-z) not in path and b == False:
#print("ygoing to"+str((x,y-z))+" by "+str(z)+" from "+str(start))
#print(self.onboard((x,y-z)))
b=self.pathsolve((x,y-z),end, path)
#print(path)
if self.onboard((x-z,y)) and (x-z,y) not in path and b == False:
#print("zgoing to"+str((x-z,y))+" by "+str(z)+" from "+str(start))
#print(end)
b=self.pathsolve((x-z,y),end, path)
# if b==True and start is not
vis.appendleft(start)
return b
需要注意的事项:
与
vis
作为参数传递并需要在整个递归搜索过程中保持其状态的方式相反,这不是path
的工作方式:它应该是一个局部变量,只接受递归调用的返回值,并在当前单元格(start
)前面加上前缀。vis
不应该是deque
,而应该是set
,这更适合于快速了解以前是否访问过某个单元格。下面是如何编写代码:
当然,这假设您的其他方法得到了很好的实现。你知道吗
看它在repl.it上运行。你知道吗
对于以下迷宫:
…从左下角开始,以右上角为目标,它给出了(x,y)坐标的路径(x=列,y=行):
相关问题 更多 >
编程相关推荐