题解 | #迷宫问题#

#include <bits/stdc++.h>

using namespace std;

int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1};
vector<pair<int, int>> res;

void dfs(vector<vector<int>>& matrix, int m, int n, int x, int y, vector<pair<int, int>>& paths){
    //一定要先压 后判断终止条件
    paths.push_back(make_pair(x, y)); //压入路径
    matrix[x][y] = 1; //标记为 已经访问过
    
    if(x == m - 1 && y == n - 1){
        res = paths;
        return;
    }

    //四个方向
    for(int i = 0; i < 4; i++){
        int mx = x + dx[i]; int my = y + dy[i];
        if(mx >= 0 && mx < m && my >= 0 && my < n && matrix[mx][my] == 0){
            dfs(matrix, m, n, mx, my, paths);
            paths.pop_back(); //回溯          
        }
    }
    matrix[x][y] = 0;
    return;  
}

int main(){
    int m = 0, n = 0;
    while(cin >> m >> n){
        vector<vector<int>> matrix(m, vector<int>(n, 0)); //
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                cin >> matrix[i][j];
            }
        }
        
        vector<pair<int, int>> paths;//记录临时路径
        //dfs
        dfs(matrix, m, n, 0, 0, paths);
        
        for(int i = 0; i < res.size(); i++){
            cout << "(" << res[i].first << "," << res[i].second << ")" << endl;
        }
        
    }
    
    return 0;
}