用图搜索方法求解迷宫问题目的：深入掌握图便利算法在求解实际问题中的应用。内容：编写一个程序exp8.cpp，完成以下功能。①建立一个迷宫对应的邻接表表示。②采用深度优先遍历算法输出从入口（1,1）到出口（M，N）的所有迷宫路径。

好的，这是一个关于迷宫问题的具体实现。下面是一些代码示例和解释，帮助你更好地理解这个问题的解决方案。

首先，我们需要将迷宫转换为邻接表的形式，以便进行深度优先遍历。邻接表是一种表示图的数据结构，它由一系列节点和连接它们的边组成，每个节点包含与之相邻的节点的列表。

在这个问题中，我们可以将每个迷宫的格子看作是一个节点，如果两个格子相邻且可以通过，则它们之间有一条边。因此，我们可以通过建立邻接表来表示迷宫。具体实现方式如下：

#include <iostream>
#include <vector>

using namespace std;

// 定义迷宫的大小为 M 行 N 列
const int M = 5;
const int N = 5;

// 定义迷宫的邻接表
vector<int> maze[M*N];

// 定义迷宫的入口和出口
int start = 0;
int end = M*N - 1;

// 将迷宫转换为邻接表
void buildMaze() {
    // 定义迷宫的地图，0 表示可以通过的格子，1 表示障碍物
    int map[M][N] = {
        {0,1,0,0,0},
        {0,1,0,1,0},
        {0,0,0,0,0},
        {0,1,1,1,0},
        {0,0,0,1,0}
    };

    // 将每个格子转换为一个节点，构建邻接表
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            int node = i*N + j;  // 将二维坐标转换为一维坐标，方便存储和访问
            if (map[i][j] == 0) {
                // 如果当前格子可以通过，添加相邻的格子作为邻居节点
                if (i > 0 && map[i-1][j] == 0) {
                    int neighbor = (i-1)*N + j;
                    maze[node].push_back(neighbor);
                }
                if (i < M-1 && map[i+1][j] == 0) {
                    int neighbor = (i+1)*N + j;
                    maze[node].push_back(neighbor);
                }
                if (j > 0 && map[i][j-1] == 0) {
                    int neighbor = i*N + j-1;
                    maze[node].push_back(neighbor);
                }
                if (j < N-1 && map[i][j+1] == 0) {
                    int neighbor = i*N + j+1;
                    maze[node].push_back(neighbor);
                }
            }
        }
    }
}

上面的代码中，我们首先定义了迷宫的大小和邻接表，然后将迷宫的地图转换为邻接表的形式。对于每个可以通过的格子，我们遍历其相邻的格子，并将其添加到邻接表中。

接下来，我们需要实现深度优先遍历算法来输出从入口到出口的所有路径。深度优先遍历是一种递归算法，它从某个节点开始，沿着一条路径遍历到底，然后回溯到之前的节点，尝试其他路径。我们可以用一个数组记录当前路径上的节点，并在遍历完一条路径后将其弹出。

具体实现方式如下：

// 定义一个数组记录当前路径
int path[M*N];
int pathLen = 0;

// 深度优先遍历输出所有路径
void dfs(int node) {
    path[pathLen++] = node;  // 将当前节点加入路径
    if (node == end) {
        // 如果当前节点是出口，输出路径
        for (int i = 0; i < pathLen; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    } else {
        // 否则继续遍历相邻节点
        for (int i = 0; i < maze[node].size(); i++) {
            int neighbor = maze[node][i];
            if (neighbor != start && find(path, path+pathLen, neighbor) == path+pathLen) {
                // 如果相邻节点不是入口并且没有在当前路径中出现过，继续遍历
                dfs(neighbor);
            }
        }
    }
    pathLen--;  // 回溯，弹出当前节点
}

上面的代码中，我们首先定义了一个路径数组和长度，用于记录当前路径。然后实现了深度优先遍历算法，其中，如果当前节点是出口，我们输出路径；否则，我们遍历其相邻节点，并继续遍历相邻节点的相邻节点，直到找到出口或者遍历完所有路径。

最后，我们可以在主函数中调用上述两个函数，输出所有路径：

int main() {
    buildMaze();
    dfs(start);
    return 0;
}

完整代码如下：