【Python】牛客HJ43迷宫问题

牛客 HJ43 —— 《迷宫问题》

总体思路：

（1）迷宫：用Graph来表示，Graph以邻接表的形式储存。

（2）顶点：每个顶点以键值对的形式存在邻接表中，邻接表的键是顶点坐标（行，列）。值是保存该顶点信息的子字典，这个子字典需要保存的信息有：该顶点的值value（字符串形式）、该顶点的相邻顶点的坐标neighbors（列表形式）。

最后邻接表应该是这种形式：

{
    (0,0): {'value': '0', 'neighbors': [(0,1)]},
    (0,1): {'value': '1', 'neighbors': [(0,0), (0,2), (1,1)]},
    ...
    (4,4): {'value': '0', 'neighbors': [(3,4), (4,3)]},
}
1
2
3
4
5
6

（3）走迷宫的过程：DFS，深度优先搜索，不清楚什么是DFS的可以看这篇文章文末：Python数据结构与算法。简单来说就是利用递归，用for循环遍历某个点周围的neighbors，只要它还有neighbors，就会移动到它的neighbor，进入下一层递归中。每走一步就把该点坐标加入result列表中，直到走到终点或死路。

这里有三个大问题：

• 走到死路后会走回头路，此时理应从列表中把回头路删掉。
• 上一步刚走的路不应该加入下一步的for循环，否则就来回走，无限递归了。
• 走到终点后就不用再递归了，应该把递归停掉。

解决方案：

• 能走回头路的，肯定是for循环执行结束，再没有neighbors能走的点，所以这些点的for循环理应是执行完了的。而不走回头路的点，for循环应该并没有执行完，还在执行更深层的递归。所以在for循环结束后加一个result.pop()，只要执行完for循环，就说明在走回头路了，移除该点。
• 加入一个last_loc变量记录上一次的位置，带着last_loc进入下层递归，并每次更新成新的坐标，这样就能避免来回打转。
• 递归终止不能用return，因为return只能停掉本层递归，还有上层递归。用全局变量控制递归内部的语句是否执行是一种办法，但并不好用！！！直接raise error，然后在递归最外面套一层异常捕获。

（4）注意事项：不要在函数内部打印结果。很多人做这道题选择在函数内部打印结果，这是因为递归的情况下要获取返回值比平常的函数要困难，原本在某个时间点，results列表已经是最短路径了，但由于递归没有及时停止，接下来执行的各种语句又把results弄乱了，导致用return总是获取不到想要的results，干脆就在函数内部打印了。所以归根结底还是递归停止的问题，raise error牛逼！！！

import sys

class Graph:
    def __init__(self):
        self.adj_list = {}
    
    def add_vertex(self, value, loc):
        # 如果该点不在邻接表中，就加进去
        if loc not in self.adj_list:
            new_vertex = {'value': value, 'neighbors': []}
            # 如果它上面/左边有点，就把两点互相加到对方的neighbors列表里
            if (loc[0]-1,loc[1]) in self.adj_list:
                self.adj_list[(loc[0]-1,loc[1])]['neighbors'].append(loc)
                new_vertex['neighbors'].append((loc[0]-1,loc[1]))
            if (loc[0],loc[1]-1) in self.adj_list:
                self.adj_list[(loc[0],loc[1]-1)]['neighbors'].append(loc)
                new_vertex['neighbors'].append((loc[0],loc[1]-1))
            self.adj_list[loc] = new_vertex
        return True

    def dfs(self, rows, cols, last_loc=None):
        result = []
        def traversal(loc, last_loc):
            # 每次递归先将本次坐标加入result列表中
            result.append(loc)
            # 如果本次位置已经是终点，就引发错误中断递归
            if loc == (rows-1, cols-1):
                raise KeyboardInterrupt
			
            # 遍历neighbors
            for neighbor in self.adj_list[loc]['neighbors']:
                # 如果neighbor不是上次刚走过的点，也不是墙壁，就进入下层递归
                if neighbor != last_loc and self.adj_list[neighbor]['value'] != '1':
                    traversal(neighbor, loc)
			
            # 如果遍历结束了，就说明这个点是个死路，该从result列表中移除
            result.pop()

        try:
            # 调用递归
            traversal((0,0), last_loc)
        except KeyboardInterrupt:
            # 如果遇到了之前函数中引发的错误，就返回result列表
            return result
        else:
            # 如果没有遇到错误，就返回：没找到终点
            return f'Location {(rows-1, cols-1)} Not Found'


# 获取迷宫深度、宽度
depth, breadth = map(int, sys.stdin.readline().strip().split(' '))
total = []
# 以列表形式保存迷宫信息
for row in range(depth):
    total.append(sys.stdin.readline().strip().split(' '))

# 实例化Graph对象并构建邻接表
graph = Graph()
for row in range(depth):
    for col in range(breadth):
        graph.add_vertex(value=total[row][col], loc=(row,col))

# 开始DFS，获取结果、打印结果        
results = graph.dfs(rows=depth, cols=breadth)
print('\n'.join([f'({loc[0]},{loc[1]})' for loc in results]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65