图论邻接矩阵解决迷宫问题

图论中的邻接矩阵可以用来解决迷宫问题。迷宫可以看作是一个二维的网格，其中的每个格子可以表示为图的一个顶点。邻接矩阵可以用来表示图中的边关系，即哪些顶点是相邻的。

在解决迷宫问题时，可以将迷宫的每个格子都看作是图的一个顶点。如果两个格子是相邻的，那么它们之间就存在一条边。通过构建迷宫的邻接矩阵，可以方便地表示迷宫中各个格子之间的关系。

使用邻接矩阵解决迷宫问题的基本思路是，首先将迷宫转化为一个图，然后使用图的搜索算法（如深度优先搜索或广度优先搜索）来找到从起点到终点的路径。

具体步骤如下：
1. 将迷宫转化为一个图，其中每个格子对应图的一个顶点。如果两个格子是相邻的且都是可通行的，那么它们之间就存在一条边。
2. 构建迷宫的邻接矩阵，将相邻的格子之间的边表示为1，不相邻的格子之间的边表示为0。
3. 使用图的搜索算法（如深度优先搜索或广度优先搜索）来找到从起点到终点的路径。搜索算法可以根据邻接矩阵来确定顶点之间的关系，并进行相应的搜索操作。

下面是一个使用邻接矩阵解决迷宫问题的示例代码：

# 定义迷宫的邻接矩阵
maze = [
    [1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 0, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
]

# 定义起点和终点的坐标
start = (1, 1)
end = (3, 3)

# 定义搜索函数
def dfs(maze, start,):
    stack = [start]  # 使用栈来保存待搜索的顶点
    visited = set()  # 使用集合来保存已访问过的顶点

    while stack:
        x, y = stack.pop()  # 弹出栈顶顶点
        visited.add((x, y))  # 将顶点标记为已访问

        if (x, y) == end:  # 判断是否到达终点
            return True

        # 遍历相邻的顶点
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] == 0 and (nx, ny) not in visited:
                stack.append((nx, ny))  # 将相邻顶点加入栈中

    return False

# 调用搜索函数
if dfs(maze, start, end):
    print("迷宫有解")
else:
    print("迷宫无解")