题解 | #迷宫问题#

```#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<vector<int>> maze;
vector<vector<int>> path;
vector<vector<int>> result;
void dfs(int i,int j){
    if(i<0||i>=n||j<0||j>=m||maze[i][j]==1){//碰到边缘或者墙壁
        return;
    }
    maze[i][j]=1;//如果可以走，这个格子走过记为1。
    path.push_back({i,j});//在记录当前路径的vector中压入此点。
    //由于题中迷宫只有一条路，只要走得通，必然能走到。
    if(i==n-1&&j==m-1){//如果走到了，就把reach位记录为true同时跳出
        result=path;
    }
    dfs(i-1,j);
    dfs(i+1,j);
    dfs(i,j-1);
    dfs(i,j+1);
    //尝试向以上四个方向走,如果四个方向都走不通就返回了，下面处理返回的情况：
     maze[i][j]=0;//将此节点置为0
     path.pop_back();//从路径中删除此节点。
}

int main(){
    while(cin>>n>>m){
        maze=vector<vector<int>>(n,vector<int>(m,0));//初始化迷宫，
        //迷宫是一个vector嵌套vector,maze包含了n个vector，每个vector存了m个初值为0的int
        //相当于a[m][n]
        path.clear();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>maze[i][j];
            }
        }
        dfs(0,0);
        vector<vector<int>>::iterator iter;
        for(iter=result.begin();iter!=result.end();iter++){
            cout<<'('<<(*iter)[0]<<','<<(*iter)[1]<<')'<<endl;
        }
    }
}