题解 | #迷宫问题#

迷宫问题

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;
}

全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务