题解 | 迷宫问题

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

vector<vector<int>> path;
vector<vector<int>> dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
bool found = false;

void dfs(vector<vector<int>>& maze, int x, int y) {
    int h = maze.size();
    int w = maze[0].size();

    maze[x][y] = 1;
    path.push_back({x, y});
    if(x == h-1 && y == w-1) {
        found = true;
        return ;
    }   

    for(int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(xx >= 0 && yy >= 0 && xx < h && yy < w && !maze[xx][yy]){
            dfs(maze, xx, yy);
            if(found) return ;
        }
    }
    path.pop_back();
}

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<int>> maze(h, vector<int>(w, 0));
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            cin >> maze[i][j];
        }
    }
    path.clear();

    dfs(maze, 0, 0);
    for(auto p: path) {
        cout << "(" << p[0] << "," << p[1] << ")" << endl;
    }
    return 0;
}