题解 | #迷宫问题#

#include <iostream>
#include <utility>
#include<vector>
using namespace std;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
vector<pair<int,int>> stk;
void dfs(vector<vector<int>>& maze, int sx, int sy, int tx, int ty, vector<pair<int, int>>& path)
{
    maze[sx][sy] = 1;
    path.push_back(make_pair(sx, sy));
    // cout << sx << " " << sy << " " << path.size() << endl;
    if(sx == tx && sy == ty) {
        stk = path;      // 要用替身，不然搞不到结果
        return;
    }
    int x = sx, y = sy;
    for(int i = 0; i < 4; ++i)
    {
        x += dx[i];
        y += dy[i];
        if(x >= 0 && x <= tx && y >= 0 && y <= ty && maze[x][y] == 0){
            dfs(maze,x,y,tx,ty, path);
        }
        x -= dx[i];        // 此处也要回溯
        y -= dy[i];
    }
    path.pop_back();
    maze[sx][sy] = 0;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> maze(n, vector<int>(m, 0));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cin >> maze[i][j];
    vector<pair<int, int>> path;
    dfs(maze, 0, 0, n-1, m-1, path);
    for(int i = 0; i < stk.size(); ++i)
    {
        cout << "(" << stk[i].first << "," << stk[i].second << ")" << endl;
    }
}