题解 | #迷宫问题#

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

vector<pair<int, int> > res;
void dfs(vector<vector<int>>& matrix, int n, int m, int i, int j, vector<pair<int, int>>& paths){
    paths.push_back(make_pair(i, j)); //记入路径
    matrix[i][j] = 1; //经过部分设置为1，表示后续不能经过
    if(i == n - 1 && j == m - 1){ //到达终点
        res = paths;
        return;
    }
    //四个方向搜索
    if(i + 1 < n && matrix[i + 1][j] == 0)
        dfs(matrix, n, m, i + 1, j, paths);
    if(j + 1 < m && matrix[i][j + 1] == 0)
        dfs(matrix, n, m, i, j + 1, paths);
    if(i - 1 >= 0 && matrix[i - 1][j] == 0)
        dfs(matrix, n, m, i - 1, j, paths);
    if(j - 1 >= 0 && matrix[i][j - 1] == 0)
        dfs(matrix, n, m, i, j - 1, paths);
    paths.pop_back(); //回溯
    matrix[i][j] = 0; 
}
int main(){
    int n, m;
    while(cin >> n >> m){
        vector<vector<int> > matrix(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) //输入迷宫矩阵
                cin >> matrix[i][j];
        vector<pair<int, int> > paths; //记录临时路径
        dfs(matrix, n, m, 0, 0, paths); //dfs遍历矩阵
        for(int i = 0; i < res.size(); i++) //输出路径
            cout << "(" << res[i].first << "," << res[i].second << ")" << endl;
    }
    return 0;
}