迷宫路径搜索算法 - 深度优先搜索(DFS)实现

这是一个经典的深度优先搜索（DFS）问题。我们可以使用递归的方式来解决。\n\n首先，我们定义一个二维数组maze来表示迷宫，其中0表示可通，1表示不可通。我们还定义一个二维数组visited来表示是否已经访问过某个格子。\n\n然后，我们可以编写一个递归函数dfs来进行深度优先搜索。在dfs函数中，我们首先判断当前格子是否是出口，如果是，则说明找到了一条路径，我们将路径总数加1。然后，我们依次尝试向上、右上、右、右下、下、左下、左、左上八个方向移动，如果移动后的格子是可通的且未访问过，则继续递归搜索。搜索完成后，我们需要将格子的访问状态恢复，以便搜索其他路径。\n\n最后，我们在主函数中调用dfs函数，并输出路径总数。\n\n下面是一种可能的实现方式（使用C++语言）：\n\ncpp\n#include <iostream>\nusing namespace std;\n\nconst int N = 5; // 迷宫的大小\nint maze[N][N] = {{0, 0, 1, 0, 0},\n {0, 0, 0, 0, 0},\n {0, 1, 0, 1, 0},\n {0, 1, 0, 0, 0},\n {0, 0, 0, 1, 0}};\nbool visited[N][N] = {false};\nint count = 0;\n\nvoid dfs(int x, int y) {\n if (x == 0 && y == N-1) { // 到达出口\n count++;\n return;\n }\n visited[x][y] = true;\n \n // 尝试向上、右上、右、右下、下、左下、左、左上八个方向移动\n int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};\n int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};\n for (int i = 0; i < 8; i++) {\n int nx = x + dx[i];\n int ny = y + dy[i];\n if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && maze[nx][ny] == 0) {\n dfs(nx, ny);\n }\n }\n \n visited[x][y] = false; // 恢复格子的访问状态\n}\n\nint main() {\n dfs(0, 0); // 从入口开始搜索\n cout << count << endl; // 输出路径总数\n return 0;\n}\n\n\n对于给定的迷宫，上述代码的输出结果为2，表示存在两条从入口到出口的路径。