题解 | 迷宫问题

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105];
int dx[]={0,-1,1,0};
int dy[]={1,0,0,-1};
struct node{
    int x,y;
};
bool vis[105][105];
bool g=false;
vector<node> q;

void dfs(int x,int y)
{  if(g)return;
   if(x==n-1&&y==m-1)
   {g=true;
    for(int i=0;i<(int)q.size();i++)
    {
        cout<<'('<<q[i].x<<','<<q[i].y<<')'<<endl;
    }return;
   }
   for(int i=0;i<4;i++)
   {
    int xx=x+dx[i];
    int yy=y+dy[i];
    if(a[xx][yy]==1)continue;
    if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy])
    {
        vis[xx][yy]=true;
        q.push_back({xx,yy});
        dfs(xx,yy);
        q.pop_back();
        vis[xx][yy]=false;
    }
   }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    q.push_back({0,0});
    vis[0][0]=true;
    dfs(0,0);
}

#牛客春招刷题训练营#https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fwww.nowcoder.com%2Fdiscuss%2F726480854079250432

//很朴素的迷宫问题，其中需要注意的几个点我说一下，我这里采用的结构体加vector的方式存储这个路径，

//然后这里的路径跟vis的回溯很重要，要时刻记得。然后是dfs(0,0)之前要vis起点