题解 | #迷宫问题# C++ 回溯

迷宫问题

https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& puzzle,
         int i, int j, vector<pair<int, int>>& path,
         vector<pair<int, int>>& res) {
    int m = (int)puzzle.size();
    int n = (int)puzzle[0].size();
    if (i < 0 || i >= m || j < 0 || j >= n || puzzle[i][j] == 1) {
        return;
    }
    puzzle[i][j] = 1; // 访问过
    path.emplace_back(i, j);
    if ((i == m - 1 && j == n - 1)) {
        res.assign(path.begin(), path.end());
        return;
    }
    vector<pair<int, int>> dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    for (const auto& p : dir) {
        int newi = p.first + i;
        int newj = p.second + j;
        dfs(puzzle, newi, newj, path,res);
    }
    puzzle[i][j] = 0;
    path.pop_back();
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> puzzle(m, vector<int>(n, 0));
    vector<pair<int, int>> path;
    vector<pair<int, int>> res;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> puzzle[i][j];
        }
    }

    dfs(puzzle, 0, 0, path, res);
    for (auto& p : res) {
        cout << "(" << p.first << "," << p.second << ")" << endl;
    }
    return 0;
}

全部评论

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
仁者伍敌:难怪小公司那么挑剔,让你们这些大佬把位置拿了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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