题解 | #迷宫问题#

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
//源码源于摸鱼学大师，细微变化
vector<pair<int,int> > res;//存储路径结果
vector<vector<bool> > visited(10,vector<bool>(10,false));;//记录访问过的节点 初始化节点均为未访问过

void DFS(vector<vector<int> > mat, int r, int c, int i, int j,vector<pair<int,int> > path);

int main() {
    int row,col;
    while(cin >> row >> col){
        vector<vector<int> > matrix(row,vector<int>(col,0));//存储迷宫矩阵
        
        for(int i = 0; i < row; i++){
            for(int j = 0; j <col; j++){
                cin >> matrix[i][j];//输入迷宫节点
            }
        }

        vector<pair<int,int> > path;//记录临时路径
        DFS(matrix,row,col,0,0,path);//从（0，0）开始

        for(int i = 0; i < res.size(); i++){//按存储顺序输出即可
            cout << '(' << res[i].first << ',' << res[i].second << ')' << endl;
        }
    }
}
void DFS(vector<vector<int> > mat, int r, int c, int i, int j, vector<pair<int,int> > path){
    path.push_back(make_pair(i,j));//将节点坐标存入临时路径
    if(i == r - 1 && j == c - 1){
        res = path;
        return ;
    }
    visited[i][j] = true;//将要访问的结点设为访问过，以免后续重复访问
    //不能用else if 衔接这样遇到样例1一旦到边界一侧没通过，递归返回（0，0）后直接结束，不会向其他方向走
    if(i + 1 < r && mat[i+1][j] == 0 && visited[i+1][j] == false)//竖着向下走
        DFS(mat,r,c,i+1,j,path);
    if(i - 1 >= 0 && mat[i-1][j] == 0 && visited[i-1][j] == false)//竖着向上走
        DFS(mat,r,c,i-1,j,path);
    if(j + 1 < c && mat[i][j+1] == 0 && visited[i][j+1] == false)//横着向右走
        DFS(mat,r,c,i,j+1,path);
    if(j - 1 >= 0 && mat[i][j-1] == 0 && visited[i][j-1] == false)//横着向左走
        DFS(mat,r,c,i,j-1,path);
}