题解 | #迷宫问题# 递归函数
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
''' 深度优先搜索(Depth-first search):可用于遍历树或者图的搜索算法,DFS与回溯法类似,一条路径走到底后需要返回上一步,搜索第二条路径。在树的遍历只中,首先一直访问到最深的节点,然后回溯到它的父节点,遍历另一条路径,直到遍历完所有节点。图也类似,如果某个节点的邻居节点都已遍历,回溯到上一个节点。 广度优先搜索(Breadth-first search):是更大范围内搜索,先访问完当前顶点的所有邻接点,然后再访问下-层的所有节点,该算法适用于解决最短、最小路径等问题,但是构建广度优先算法需要维护自己的队列。广度搜索是同时搜索所有路径,相当于一层一层地搜索,就好比波浪的扩展一样。此搜索方法跟树的层次遍历类似,因此宽度搜索一般都用队列存储结构。 ''' ''' from collections import deque def bfs(graph,start): queue=deque([start]) visited=set([start]) while queue: node=queue.popleft() # 删去最左边的元素,并返回该元素 print(node,end=' ') for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor) visited.add(neighbor) graph={ 'A':['B','C'], 'B':['A','D','E'], 'C':['A','F','G'], 'D':['B'], 'E':['B'], 'F':['C'], 'G':['C'], } bfs(graph,'A') ''' while 1: try: m,n=map(int,input().split()) maze=[] for i in range(m): row=list(map(int,input().split())) maze.append(row) #print(arr[0][0],arr[0][1],arr[1][0],type(arr[0][1])) def walk(i,j,pos=[(0,0)]): if j+1 < n and maze[i][j+1] == 0: # 向右 if (i, j+1) not in pos: walk(i, j+1, pos + [(i, j+1)]) if j-1 >= 0 and maze[i][j-1] == 0: # 向左 if (i, j-1) not in pos: walk(i, j-1, pos + [(i, j-1)]) if i+1 < m and maze[i+1][j] == 0: # 向下 if (i+1, j) not in pos: walk(i+1, j, pos + [(i+1, j)]) if i-1 >= 0 and maze[i-1][j] == 0: # 向上 if (i-1, j) not in pos: walk(i-1, j, pos + [(i-1, j)]) if (i, j) == (m-1, n-1): # 到达出口 for p in pos: print('(' + str(p[0]) + ',' + str(p[1]) + ')') walk(0,0) except: break