题解 | #迷宫问题#

迷宫问题

https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

path = []
# load data from ex.
m,n = map(eval,input().split())
maze = []
for i in range(m):
    maze.append(list(map(eval,input().split())))
# struct of the cord
class pos:
    def __init__(self,x,y):
        self.x = x 
        self.y = y
# implement the dfs
def dfs(maze,x,y,path):
    path.append(pos(x,y))
    maze[x][y]=1
    # dfs 返回 true 表示遍历到了结果
    if x==(len(maze)-1) and y==(len(maze[0])-1):
        return True
    # 从四个方向检查是否满足边界约束/墙体约束
    if x-1>=0 and maze[x-1][y]==0:
        if dfs(maze,x-1,y,path):
            return True
    if x+1<len(maze) and maze[x+1][y]==0:
        if dfs(maze,x+1,y,path):
            return True
    if y-1>=0 and maze[x][y-1]==0:
        if dfs(maze,x,y-1,path):
            return True
    if y+1<len(maze[0]) and maze[x][y+1]==0:
        if dfs(maze,x,y+1,path):
            return True
    path.pop()
    maze[x][y] = 0
    return False
# main
dfs(maze,0,0,path)
for i in range(len(path)):
    print(f"({path[i].x},{path[i].y})")

全部评论

相关推荐

身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
ohs的小木屋:比不少实习待遇高了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务