题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
#include <iostream> #include <utility> #include <vector> using namespace std; int m, n; vector<pair<int, int>> result; vector<pair<int, int>> path; void dfs(vector<vector<int>>& maze, int x, int y) { //将该点加入路径 path.push_back(make_pair(x, y)); maze[x][y] = 1; //到终点了,返回路径 if (x == m - 1 && y == n - 1) { result = path; return; } //右行 if (x+1 < m && maze[x + 1][y] == 0) dfs(maze, x + 1, y); //左行 if (x-1 >= 0 && maze[x - 1][y] == 0) dfs(maze, x - 1, y); //下行 if (y+1 < n && maze[x][y + 1] == 0) dfs(maze, x, y + 1); //上行 if (y-1 >= 0 && maze[x][y - 1] == 0) dfs(maze, x, y - 1); //回溯 path.pop_back(); maze[x][y] = 0; } int main() { while (cin >> m >> n) { vector<vector<int>> maze(m, vector<int>(n)); //创建迷宫 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> maze[i][j]; } } //从起点开始 dfs(maze, 0, 0); for (int i = 0; i < result.size(); i++) { cout << "(" << result[i].first << "," << result[i].second << ")" << endl; } } return 0; }