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

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> res;
vector<vector<int>> path;
void dfs(int x, int y, vector<vector<int>> &map)
{
    path.push_back({x,y});
    map[x][y] = 1;
    if(x == map.size() - 1 && y == map[0].size() - 1)
    {
        res = path;
        return;
    }
    if(x + 1 < map.size() && map[x + 1][y] == 0)
    {
        dfs(x + 1, y, map);
    }
    if(y + 1 < map[0].size() && map[x][y + 1] == 0)
    {
        dfs(x, y + 1, map);
    }
    if(x - 1 >= 0 && map[x - 1][y] == 0)
    {
        dfs(x - 1, y, map);
    }
    if(y - 1 >= 0 && map[x][y - 1] == 0)
    {
        dfs(x, y - 1, map);
    }
    path.pop_back();
    map[x][y] = 0;
}

int main()
{
    int row, column;
    cin >> row >> column;
    vector<vector<int>> map(row, vector<int>(column));
    for(int i = 0; i < row; ++i)
    {
        for(int j = 0; j < column; ++j)
        {
            cin >>  map[i][j];
        }
    }
    dfs(0, 0, map);
    for(int i = 0; i < res.size(); ++i)
    {
        cout << "(" << res[i][0] << "," << res[i][1]<< ")" << endl;
    }
    return 0;
}