题解 | 迷宫寻路 DFS

#include<iostream>
#include<cstring>
using namespace std;

int n,m;          
char a[1005][1005];
bool flag=false;  // 标记是否找到从(1,1)到(n,m)的路径
bool f[1005][1005];
void dfs(int x,int y)
{
   // 到达终点(n,m)，返回
   if(x==n&&y==m)
   {
    flag=true;
    return;
   }
   // 已找到路径，直接返回
   if(flag==true)
   {
    return;
   }
   // 边界/合法性检查
   if(x<1||x>n||y<1||y>m||a[x][y]=='#'||f[x][y]==true)
   {
    return;
   }
   f[x][y]=true;          
   dfs(x-1,y);            
   dfs(x,y+1);            
   dfs(x+1,y);          
   dfs(x,y-1);           
}
int main(void)
{
    memset(f,false,sizeof(f));
    
    cin>>n>>m;               
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    
    dfs(1,1);              
    if(flag==true)
    {
        cout<<"Yes";
    }
    else {
        cout<<"No";
    }
    return 0;
}