题解 | #迷宫问题#

#include 
using namespace std;
//每个点都有两种走法：在有路的情况下，向右(i,j+1),向下(i+1,j),到(n-1,m-1)成功
//用数组来记录路径
vector> route;
vector> temp_path;
vector> best_path;
void dfs(int i,int j,int n,int m){
    //处理走不通的情况:数组越界；碰到墙壁或者已经走过
    if(in-1||jm-1||route[i][j]==1){
        return;
    }
    route[i][j]=1;//标记该位置已走过
    temp_path.push_back({i,j});
    if(i==n-1&&j==m-1){
        /*有多条路径时最小的temp_path则为best_path,
        但该题中只有唯一路径，因此可以直接将best等于temp
        if(temp_path.size()<best_path.size()||best_path.empty())
            best_path=temp_path;
        */
        best_path=temp_path;
    }
    dfs(i-1,j,n,m);//上
    dfs(i+1,j,n,m);//下
    dfs(i,j-1,n,m);//左
    dfs(i,j+1,n,m);//右
    //如果能成功的话到这一步为止就会跳出去，因为走不通所以会运行到下面
    route[i][j]=0;//该节点走不通时，在回溯中要恢复成原来的状态
    temp_path.pop_back();//从路径中删除该节点
}
int main() {
    int n,m;
    while(cin>>n>>m){
        route=vector>(n,vector(m,0));//设置地图大小并初始化
        //一次测试多个案例依次输入，每个案例执行完后将容器清空
        best_path.clear();
        temp_path.clear();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>route[i][j];
            }
        }
        dfs(0,0,n,m);
        vector>:: iterator it;
        for(it=best_path.begin();it!=best_path.end();it++)
            cout<<'('<<(*it)[0]<<','<<(*it)[1]<<')'<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")