题解 | 迷宫寻路

#include<bits/stdc++.h>
using namespace std;
bool found=false;
int m,n;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char a[100][100];
int v[100][100];
void dfs(int x,int y){
    if(x==n&&y==m){
        found=1;
        return;
    }
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(a[nx][ny]=='.'&&v[nx][ny]==0&&1<=nx&&nx<=n&&1<=ny&&ny<=m){
            v[nx][ny]=1;
            dfs(nx,ny);
            if(found){return;}
            v[nx][ny]=0;
           
        }
    }
}
int main() {
   cin>>n>>m;
   int startx=1,starty=1;
   for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
    }
   }
    v[1][1]=1;
    dfs(startx,starty);
    if(found){cout<<"Yes";}else{
        cout<<"No"; }
    return 0;
}