题解 | #迷宫问题#

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int m,n;
bool flag=0;//表示是否到达了终点
vector<vector<int>> ans;//记录路径答案
void dfs(int i,int j,vector<vector<bool>> st,vector<vector<int>> map){
    st[i][j]=1;
    if(i==m&&j==n){
        flag=1;//表示已到达终点
        ans.push_back({i-1,j-1});//记录
        return;
    }
    if(!st[i][j+1]&&map[i][j+1]==0&&!flag){//到达终点前，遇见可以走的路就要走
        dfs(i,j+1,st,map);
    }
    if(!st[i][j-1]&&map[i][j-1]==0&&!flag){//到达终点前，遇见可以走的路就要走
        dfs(i,j-1,st,map);
    }
    if(!st[i+1][j]&&map[i+1][j]==0&&!flag){//到达终点前，遇见可以走的路就要走
        dfs(i+1,j,st,map);
    }
    if(!st[i-1][j]&&map[i-1][j]==0&&!flag){//到达终点前，遇见可以走的路就要走
        dfs(i-1,j,st,map);
    }
    if(flag) ans.push_back({i-1,j-1});//到达终点之后，返回时记录路径
    return;
}
int main() {
    cin>>m>>n;
    vector<vector<int>> map(m+2,vector<int>(n+2));//记录迷宫
    vector<vector<bool>> st(m+2,vector<bool>(n+2));//记录当前是否已经到达过
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>map[i][j];
        }
    }
    for(int i=0;i<m+2;i++){
        map[i][0]=1;
        map[i][n+1]=1;
    }
    for(int j=0;j<n+2;j++){
        map[0][j]=1;
        map[m+1][j]=1;
    }//初始化迷宫
    dfs(1,1,st,map);//起点出发开始dfs
    for(int i=ans.size()-1;i>=0;i--){
        cout<<"("<<ans[i][0]<<","<<ans[i][1]<<")"<<endl;//倒序打印路径
    }
}