A7991.迷宫 DFS题解

这是一道经典的深搜（深度优先搜索，DFS）模板题（虽然我用了AC助手才AC的）。

1. 思路：

1、从 起点 开始，判断每个点是否符合题目条件

2、若符合条件，则从该点开始，向四周 搜索

3、若无法继续前进，则 返回

4、若可以前进，则 前进（通过 递归 实现）

5、若到达终点，则给出相应答案并 结束

6、若无法到达终点，则给出相应答案并 退出

2. 完整代码：

#include<bits/stdc++.h>
//pretreatment
#define N 1000
#define ll long long
#define ull unsigned long long
#define endl '\n'
using namespace std;
// variables setting
ull n,ha,la,hb,lb,m;
bool vis[110][110];
char mp[110][110];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
// functions(others) defining
void dfs(int x,int y)
{
    if(x==hb&&y==lb)
    {
        cout<<"YES"<<endl;
        exit(0);
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&mp[nx][ny]=='.')
        {
            vis[nx][ny]=true;
            dfs(nx,ny);
        }
    }
}
// the program subject
void program()
{
    cin>>n>>m;cin>>ha>>la>>hb>>lb;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mp[i][j];
        }
    }
    vis[ha][la]=true;
    dfs(ha,la);
    cout<<"NO"<<endl;
}
// the main function
int main()
{
    program();
    return 0;
}