Python 迷宫生成器和解迷宫算法：DFS 搜索实现

这段代码实现了一个迷宫生成器和解迷宫的功能。具体实现如下：

迷宫生成

首先，定义了一个M*N大小的迷宫矩阵maze，并用1初始化所有值，相当于墙。然后，使用随机函数生成0或1，0表示通路，1表示墙，将其赋值给maze矩阵。随后，将迷宫的入口(1,1)和出口(M,N)设为通路。

接着，使用DFS搜索算法检查迷宫是否存在通路。具体实现是，先定义一个visited集合，表示已经访问过的节点。然后，从起点(1,1)开始，递归地遍历其所有邻居节点，如果邻居节点未被访问过，就将其加入visited集合，并继续递归遍历。如果遍历到终点(M,N)，就返回True，表示存在通路。否则，返回False。

为了方便DFS搜索，还需要建立邻接表adj_list，表示每个节点的邻居节点。具体实现是，遍历maze矩阵中的每个节点，如果该节点为墙，则跳过；否则，检查该节点的四个邻居节点，如果邻居节点为通路，则将其加入该节点的邻居列表中。最后，将邻接表存储在字典adj_list中。

如果DFS搜索发现存在通路，则退出循环，生成的迷宫矩阵maze和邻接表adj_list即为所求。

解迷宫

首先，定义了一个dfs_search_all_paths函数，用于搜索所有从起点到终点的路径。具体实现是，从起点(1,1)开始，递归地遍历其所有邻居节点，如果邻居节点未被访问过，就将其加入visited集合，并继续递归遍历。如果遍历到终点(M,N)，就返回一个包含终点的列表。否则，遍历所有邻居节点，并将它们的路径加入到paths列表中。最后，返回所有路径的列表。

接着，调用dfs_search_all_paths函数，搜索所有从起点到终点的路径，并将其打印出来。具体实现是，遍历所有路径，将其反转并用' -> '连接起来，然后打印出来。

综上所述，这段代码实现了一个简单的迷宫生成器和解迷宫的功能，使用了DFS搜索算法和邻接表数据结构。

import random

M = 5
N = 5

while True:
    # 生成迷宫矩阵
    maze = [[1 for j in range(N + 2)] for i in range(M + 2)]  # 用1初始化所有值，相当于墙
    for i in range(1, M + 1):
        for j in range(1, N + 1):
            maze[i][j] = random.randint(0, 1)  # 随机生成0或1，0表示通路，1表示墙

    # 入口和出口必须为通路
    maze[1][1] = 0
    maze[M][N] = 0

    # DFS搜索，检查是否存在通路
    visited = set()

    def dfs_search(start):
        visited.add(start)
        if start == (M, N):
            return True
        for neighbor in adj_list[start]:
            if neighbor not in visited:
                if dfs_search(neighbor):
                    return True
        return False

    # 建立邻接表
    adj_list = {}
    for i in range(1, M + 1):
        for j in range(1, N + 1):
            if maze[i][j] == 1:
                continue
            neighbors = []
            if i > 1 and maze[i - 1][j] == 0:  # 左
                neighbors.append((i - 1, j))
            if i < M and maze[i + 1][j] == 0:  # 右
                neighbors.append((i + 1, j))
            if j > 1 and maze[i][j - 1] == 0:  # 上
                neighbors.append((i, j - 1))
            if j < N and maze[i][j + 1] == 0:  # 下
                neighbors.append((i, j + 1))
            adj_list[(i, j)] = neighbors

    if dfs_search((1, 1)):
        break

# 输出迷宫矩阵
for i in range(1, M + 1):
    for j in range(1, N + 1):
        if maze[i][j] == 0:
            print('0', end=' ')
        else:
            print('1', end=' ')
    print()

# 输出邻接表
for node, neighbors in adj_list.items():
    print(node, '->', neighbors)

# DFS搜索所有路径
def dfs_search_all_paths(start, end, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    if start == end:
        return [[end]]
    paths = []
    for neighbor in adj_list[start]:
        if neighbor not in visited:
            sub_paths = dfs_search_all_paths(neighbor, end, visited)
            if sub_paths:
                for sub_path in sub_paths:
                    paths.append(sub_path + [start])
    return paths

print('所有路径：')
dfs_all_path = dfs_search_all_paths((1, 1), (M, N))
for path in dfs_all_path:
    path.reverse()
    print(' -> '.join(str(step) for step in path))