题目描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

注意：A、B不一定是两个不同的点。

输入格式
第1行是测试数据的组数 k，后面跟着 k 组输入。

每组测试数据的第1行是一个正整数 n，表示迷宫的规模是 n∗n 的。

接下来是一个 n∗n 的矩阵，矩阵中的元素为.或者#。

再接下来一行是 4 个整数 ha,la,hb,lb，描述 A 处在第 ha 行, 第 la 列，B 处在第 hb 行, 第 lb 列。

注意到 ha,la,hb,lb 全部是从 0 开始计数的。

输出格式
k行，每行输出对应一个输入。

能办到则输出“YES”，否则输出“NO”。

数据范围
1≤n≤100

样例

输入样例：

2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

输出样例：
YES
NO

dfs

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
char g[N][N];
bool st[N][N];
int n;
int sx,sy,ex,ey;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool dfs(int a,int b)
{
    if(g[a][b]=='#') return false;//每次进入dfs前先判断搜的点是否合法,不合法说明当前层不能搜，直接返回上一层,去寻找新的可能性

    //if(a<0||b<0||a>=n||b>=n) return false;//不合法，返回🙅‍♂️

  //  if(st[a][b]) return false;//不合法，返回

    if(a==ex&&b==ey) return true;//判断是否已经收到终点了，收到了，返回合法

    st[a][b]=true;//标记已经搜到过了

    //经过上面重重考验还没有直接return的，说明传进来的点是合法的状态，是个可用之才👏👏，但有没有潜力，让我试你一试

    for(int i=0;i<4;i++ )
    {
        int nx=a+dx[i];//让俺来瞅瞅你这个可用之点能够走到哪一步
        int ny=b+dy[i];//放进dfs()里的nx，ny就能识别你这一步走的对不对，对，会接着走，不对，接着试试其他可能
        if(nx<0||nx>=n||ny<0||ny>=n) continue;
        if(st[nx][ny]) continue;
        if(dfs(nx,ny)) return true;
    }
    return false; //当前点是合法的，但你尝试了4个方向还是找不到可以走的下一个点，也说明这个点没有潜力，尽管你是合法的,返回上一层
}
int main()
{
    int k;
    cin>>k;
    while(k--)
    {
        cin>>n;
        for(int i=0;i<n;i++) cin>>g[i];
        cin>>sx>>sy>>ex>>ey;
        if(dfs(sx,sy)) puts("YES");
        else puts("NO");
    }
    return 0;
}