题解 | 迷宫问题 回溯算法求解具体路径

#include <iostream>
#include <vector>
using namespace std;
bool dfs(int a, int b, int h, int w, vector<pair<int, int>>& res,
         vector<vector<int>>& map) {
    if (a == h && b == w) {
        return true;
    }
    if (a > 0 && map[a - 1][b] == 0) {
        res.emplace_back(a - 1, b);
        map[a - 1][b] = 2;
        if (dfs(a - 1, b, h, w, res, map)) {
            return true;
        }
        map[a - 1][b] = 0;
        res.pop_back();
    }
    if (a < h && map[a + 1][b] == 0) {
        res.emplace_back(a + 1, b);
        map[a + 1][b] = 2;
        if (dfs(a + 1, b, h, w, res, map)) {
            return true;
        }
        map[a + 1][b] = 0;
        res.pop_back();
    }
    if (b > 0 && map[a][b-1] == 0) {
        res.emplace_back(a,b-1);
        map[a][b-1] = 2;
        if (dfs(a, b-1, h, w, res, map)) {
            return true;
        }
        map[a][b-1] = 0;
        res.pop_back();
    }
    if (b < w && map[a][b+1] == 0) {
        res.emplace_back(a, b+1);
        map[a][b+1] = 2;
        if (dfs(a,b+1, h, w, res, map)) {
            return true;
        }
        map[a][b+1] = 0;
        res.pop_back();
    }
    return false;
}
int main() {
    int h, w;
    cin >> h >> w;
    vector map(h, vector<int>(w, false));
    for (int i = 0 ; i  < h; i++) {
        for (int j = 0 ; j < w; j++) {
            cin >> map[i][j];
        }
    }
    vector<pair<int, int>> path;
    path.emplace_back(0,0);
    bool arrive = dfs(0,0,h-1,w-1,path,map);
    if (arrive) {
        for (auto[x,y] : path) {
            cout << "(" << x << ',' << y << ")" << endl;
        }
    }

}