C++ 利用 DFS 求解 10×10 以内矩阵从左上角到右下角的路径总数

要解决这个问题，我们可以使用深度优先搜索（DFS）或动态规划（DP）来计算从左上角到右下角的路径数量。由于矩阵的大小限制（n, m ≤ 10），DFS 是一个可行的选择。 以下是使用 DFS 的 C++ 代码实现： ```cpp #include <iostream> #include <vector> using namespace std; int dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& visited) { int n = grid.size(); int m = grid[0].size(); // 如果到达右下角，返回1表示找到一条路径 if (x == n - 1 && y == m - 1) { return 1; } // 如果当前位置已经访问过，返回0 if (visited[x][y]) { return 0; } // 标记当前位置为已访问 visited[x][y] = 1; int paths = 0; // 向右移动 if (y + 1 < m && grid[x][y + 1] == 0) { paths += dfs(x, y + 1, grid, visited); } // 向下移动 if (x + 1 < n && grid[x + 1][y] == 0) { paths += dfs(x + 1, y, grid, visited); } // 向左移动 if (y - 1 >= 0 && grid[x][y - 1] == 0) { paths += dfs(x, y - 1, grid, visited); } // 向上移动 if (x - 1 >= 0 && grid[x - 1][y] == 0) { paths += dfs(x - 1, y, grid, visited); } // 回溯，取消当前位置的访问标记 visited[x][y] = 0; return paths; } int main() { int n, m; cin >> n >> m; vector<vector<int>> grid(n, vector<int>(m)); vector<vector<int>> visited(n, vector<int>(m, 0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> grid[i][j]; } } int result = dfs(0, 0, grid, visited); cout << result << endl; return 0; } ``` 代码解释： 1. `dfs` 函数用于递归地搜索从当前位置 `(x, y)` 到右下角的路径数量。 2. `visited` 数组用于标记已经访问过的位置，避免重复访问。 3. 在每次递归调用中，检查四个方向（右、下、左、上）是否可以移动，并且该位置没有被访问过。 4. 如果到达右下角，返回1表示找到一条路径。 5. `main` 函数中读取输入并调用 `dfs` 函数，输出结果。 需要注意的逻辑点： 1. 确保在递归调用中正确处理边界条件，避免数组越界。 2. 使用 `visited` 数组来避免重复访问同一个位置，防止无限递归。 3. 在递归返回时，记得回溯并取消 `visited` 标记，以便其他路径可以访问该位置。 ######[AI写代码神器 | 725点数解答 | 2025-03-07 18:43:28]