题解 | 迷宫问题

#include <bits/stdc++.h>
using namespace std;

int h,w;
int v[101][101]={-1};//初始化

int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//定义方向数组
vector<pair<int ,int>>dp;//路径记录数组


void dfs(int x,int y){
    if(x==h-1&&y==w-1){
        for(int i=0;i<dp.size();i++){
            cout<<"("<<dp[i].first<<","<<dp[i].second<<")"<<'\n'; 
        } return;
    }
        for(int i=0;i<4;i++){
            if(v[x+d[i][0]][y+d[i][1]]==0&&x+d[i][0]<=h-1&&y+d[i][1]<=w-1&&x+d[i][0]>=0&&y+d[i][1]>=0){
                v[x+d[i][0]][y+d[i][1]]=1;
                dp.push_back(pair(x+d[i][0],y+d[i][1]));
                dfs(x+d[i][0],y+d[i][1]);
                v[x+d[i][0]][y+d[i][1]]=0;//回溯
                dp.pop_back();//删除dp路径
            }
            
        }
    
}


int main() {
    cin>>h>>w;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>v[i][j];
        }
    }
    // for(int i=0;i<h;i++){
    //     for(int j=0;j<w;j++){
    //         cout<<v[i][j];
    //     }
    // }
    dp.push_back(pair(0,0));
    dfs(0,0);
}
// 64 位输出请用 printf("%lld")