题解 | #迷宫问题#

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

class DFS {
public:
    int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    vector<vector<int>> res;
    vector<vector<int>> path;
    vector<vector<int>> vis;
    int m;
    int n;
    DFS(vector<vector<int>>& mat){
        m = mat.size(),n = mat[0].size();
        vis.resize(m, vector<int>(n));
        dfs(0,0,mat);
    }
    
    void dfs(int x, int y, vector<vector<int>>& mat){
        if(x < 0 || y < 0 || x >= m || y >= n || res.size() > 0){
            return;
        }
        if(vis[x][y] || mat[x][y] == 1) return;
        if(x == m - 1 && y == n - 1){
           for(int i = 0; i < path.size(); i++){
            res.push_back(path[i]);
           }
           res.push_back({x,y});
           return;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            path.push_back({x, y});
            vis[x][y] = true;
            dfs(nx,ny,mat);
            path.pop_back();
            vis[x][y] = false;
        }

    }
};


int main() {
    int m, n;
    while (cin >> m >> n) {
        vector<vector<int>> mat(m, vector<int>(n));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                cin >> mat[i][j];
            }
        }
        auto d = new DFS(mat);
        for(int i = 0; i < d->res.size(); i++){
            cout << '(' << d->res[i][0] << "," << d->res[i][1] << ')' << endl;
        } 
    }
    return 0;
}