题解 | #迷宫问题# 递归函数

迷宫问题

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

全部评论

相关推荐

许愿ssp的咸鱼很不想泡池子:import python as pyhton
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务