C++ 迷宫路径问题：深度优先搜索算法实现

{///'title///': ///'C++ 迷宫路径问题：深度优先搜索算法实现///', ///'description///': ///'本文介绍了使用深度优先搜索算法（DFS）解决迷宫路径问题的 C++ 代码。代码可以找出所有从迷宫入口（左上角）到出口（右上角）的路径，并输出路径总数。示例代码演示了如何读取迷宫数据，使用 DFS 算法遍历迷宫，并输出结果。///', ///'keywords///': ///'迷宫路径, 深度优先搜索, DFS, C++, 算法, 代码, 示例///', ///'content///': ///'# 迷宫路径问题：深度优先搜索算法实现/n/n给定一个 N*N (2<=N<10) 方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放 0 和 1，0 表示可通，1 表示不能通，入口和出口处肯定是 0。迷宫走的规则如下所示：即从某点开始，有八个方向可走，前进方格中数字为 0 时表示可通过，为 1 时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径(不能重复)，输出路径总数，如果无法到达，则输出 0。/n/n## 输入/n/n如题/n/n## 输出/n/n路径总数/n/n## C++ 代码实现/n/n以下是一个使用深度优先搜索算法（DFS）来解决迷宫路径问题的 C++ 代码：/n/ncpp/n#include <iostream>/n#include <vector>/n/nusing namespace std;/n/nint dfs(vector<vector<int>>& maze, int row, int col, int n) {/n // 当前位置为右上角，找到一条有效路径/n if (row == 0 && col == n-1) {/n return 1;/n }/n /n int count = 0;/n /n // 尝试向上、右上、右、右下等八个方向移动/n int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};/n int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};/n /n for (int i = 0; i < 8; i++) {/n int newRow = row + dx[i];/n int newCol = col + dy[i];/n /n // 判断新位置是否合法，并且新位置的值为 0/n if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && maze[newRow][newCol] == 0) {/n // 标记当前位置已经访问过，防止重复访问/n maze[newRow][newCol] = 1;/n count += dfs(maze, newRow, newCol, n);/n // 回溯，将当前位置标记为未访问过/n maze[newRow][newCol] = 0;/n }/n }/n /n return count;/n}/n/nint main() {/n int n;/n cin >> n;/n /n vector<vector<int>> maze(n, vector<int>(n));/n /n for (int i = 0; i < n; i++) {/n for (int j = 0; j < n; j++) {/n cin >> maze[i][j];/n }/n }/n /n int count = dfs(maze, n-1, 0, n);/n /n cout << count << endl;/n /n return 0;/n}/n/n/n## 输入示例：/n/n/n4/n0 0 0 0/n0 1 1 0/n0 0 0 0/n0 1 0 0/n/n/n## 输出示例：/n/n/n2/n/n/n## 代码说明/n/n该代码中，首先读取迷宫的大小和迷宫的格子内容。然后，使用深度优先搜索算法从右上角开始，尝试向八个方向移动，直到到达左上角。在搜索过程中，如果遇到不能通过的格子，会进行回溯。最终，输出找到的路径总数。/n/