题解 | 迷宫寻路

//蒟蒻第一次尝试题解，有错请指出，感谢~

这是一道模板题，初学搜索这道题感觉非常之nice

题目中给定一份图'.'表示此路可走，'#'表示此路不通

并且告诉我们旺仔哥哥要从左上走到右下点，问我们旺仔是否可以到达右下点

解题思路：

我们可以利用深搜的方法，将题目图的所有可能路径遍历一遍，用bool类型数组visited[N][N]来记录每个遍历过的点的状态。代码执行到最后，如果visited[n-1][m-1] == true;的话，代表右下点已经被遍历到了，所有旺仔可以到达，否则旺仔哥哥不能到达。

深搜的特点是每一个可以遍历的点都会遍历一遍，即一条路走到黑，在这道题中，只需要判断是否可达到终点（右下点）。

我们用char类型mp数组存储图，bool类型数组存储已经遍历的点的状态，已遍历为true，未遍历为false。

dx和dy数组表示当前点可能走的四个方向（上下左右）。

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
char mp[N][N];
int dx[4]={-1,1,0,0},//四个方向
	dy[4]={0,0,-1,1};
bool visited[N][N];//每个可遍历点的状态
void dfs(int x,int y)//深搜算法
{
    visited[x][y] = true;//将每次遍历到的点标记为true
    for(int i=0;i<4;i++)
    {
       int nx = x + dx[i], ny = y + dy[i]; //循环中四个方向会逐一排查  
        if(nx>=0 && nx<n && ny>=0 && ny<m && !visited[nx][ny] && mp[nx][ny] == '.')
		  //满足边界条件（不能超出图的范围）并且该点没被遍历过,并且为'.'
        {
            dfs(nx,ny); //递归继续往后遍历
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)//将题目所给图输入
    {
        for(int j=0;j<m;j++)
        {
            cin>>mp[i][j];
        }
    }
    dfs(0,0);//调用dfs开始遍历，旺仔哥哥出发点为（0，0）
  
  //遍历完成后得到结果
  //判断右下点是否为true，代码是0-based 注意要-1
    if(visited[n-1][m-1]) cout<<"Yes";
    else cout<<"No";
}

代码如果有错请指出，感谢~

各位有什么看法可以聊聊