题解 | 迷宫寻路

#include <bits/stdc++.h>
using namespace std;
const int N=105;
char p[N][N];//存地图
bool st[N][N];//标记是否访问
int n,m;//全局变量表示终点
bool dfs(int a,int b)//布尔值判断是否找到
{
    if(a==n-1&&b==m-1) return true;//表示已经找到
  //向下移动
     if((a+1<=n-1)&&!st[a+1][b]&&p[a+1][b]=='.')
     {
        st[a+1][b]=true;//标记访问
        if(dfs(a+1,b)) return true;//接着上一层回溯返回true
        //这里不需要回溯，不然时间超限
	   //以下同理解释
     }
  //向上移动
     if((a-1>=0)&&!st[a-1][b]&&p[a-1][b]=='.')
     {
        st[a-1][b]=true;
        if(dfs(a-1,b)) return true;
        
     }
  //向左移动
     if((b-1>=0)&&!st[a][b-1]&&p[a][b-1]=='.')
     {
        st[a][b-1]=true;
        if(dfs(a,b-1)) return true;
        
     }
  //向右移动
     if((b+1<=m-1)&&!st[a][b+1]&&p[a][b+1]=='.')
     {
        st[a][b+1]=true;
        if(dfs(a,b+1)) return true;
        
     }
     return false;//全部尝试过后没有找到
}
int main() {
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>p[i][j];
        }
    }
    st[0][0]=true;//标记初始点已经访问
    if(dfs(0,0)) cout<<"Yes";
    else cout<<"No";
    return 0;
}
// 64 位输出请用 printf("%lld")

题目重述：

背景：一个n*m的矩阵迷宫

"."表示空地，"#"表示墙

移动规则：每次只可以上下左右移动；

起点（1，1） 终点（n，m）

任务：

判断旺仔能否走出迷宫//找到一种旺仔可以走到终点的情况。

解题思想：

DFS：尝试每次移动的可能性，找到一种可能的情况。

算法设计：

1.用二维数组储存地图。

2函数返回类型布尔型。

3.访问标记 每次移动数组下标变化情况

4找到的条件if(a==n-1&&b==m-1) return true

常见错误：

1数组开小

2加了回溯//我们不需要找到所有情况，只要一种情况就可以不用回溯

3边界处理//不可以!st[a+1][b]再判断(a-1>=0)这样会导致数组访问越界

4 初始点没有标记访问st[0][0]=true;