题解 | #迷宫问题#

迷宫问题

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

inline1 = input().split(' ')
rows, cols = int(inline1[0]), int(inline1[1])
maze = []
for _ in range(rows):
    inline2 = list(map(int, input().split(' ')))
    maze.append(inline2)

from typing import Any


# rows, cols = 5, 5
# maze = [[0, 1, 0, 0, 0],
#         [0, 1, 1, 1, 0],
#         [0, 0, 0, 0, 0],
#         [0, 1, 1, 1, 0],
#         [0, 0, 0, 1, 0],]

class Solution:
    def __init__(self, maze_in, rows_in, cols_in) -> None:
        self.maze = maze_in
        self.rows = rows_in
        self.cols = cols_in
        self.path = []
    
    def explore(self, start):
        if start == [self.rows-1, self.cols-1]:
            return True
        
        # 以下每一种搜索路径不冲突,不能用elif
        # 如果有抵达路径,则一定会在以下判断中返回True,反之会走完以下所有判断返回False
        if 0 < start[0] and not self.maze[start[0]-1][start[1]]:
            self.maze[start[0]-1][start[1]] = 2
            if self.explore([start[0]-1, start[1]]):
                self.path.append([start[0]-1, start[1]])
                return True
        if start[0] < self.rows-1 and not self.maze[start[0]+1][start[1]]:
            self.maze[start[0]+1][start[1]] = 2
            if self.explore([start[0]+1, start[1]]):
                self.path.append([start[0]+1, start[1]])
                return True
        if 0 < start[1] and not self.maze[start[0]][start[1]-1]:
            self.maze[start[0]][start[1]-1] = 2
            if self.explore([start[0], start[1]-1]):
                self.path.append([start[0], start[1]-1])
                return True
        if start[1] < self.cols-1 and not self.maze[start[0]][start[1]+1]:
            self.maze[start[0]][start[1]+1] = 2
            if self.explore([start[0], start[1]+1]):
                self.path.append([start[0], start[1]+1])
                return True
        return False

    def __call__(self, start) -> Any:
        if self.maze[start[0]][start[1]] == 1:  # 判断0,0是否有可行路径
            return False
        else:
            self.maze[start[0]][start[1]] = 2
            if self.explore(start):
                self.path.append(start)
                for ptr in self.path[::-1]:
                    print('({},{})'.format(*ptr))
            else:
                return False


sol = Solution(maze, rows, cols)
sol([0, 0])

关键在于递归终止条件的写法,任一个路径如果递归抵达返回True,所有路径都不能递归抵达则返回False

全部评论

相关推荐

05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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