acwing1112. 迷宫

题目

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

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

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

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

题解

#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
char g[N][N];
bool st[N][N];
int n;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool dfs(int x,int y,int ex,int ey){
    if(g[x][y]=='#')return false;
    if(x==ex&&y==ey){
        return true;
    }
    st[x][y]=true;
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=n)continue;
        if(st[a][b])continue;
        if(dfs(a,b,ex,ey))return true;
    }
    return false;
}
int main(){
    int k;
    cin>>k;
    while(k--){
        cin>>n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>g[i][j];
        int x,y,ex,ey;
        cin>>x>>y>>ex>>ey;
        memset(st,false,sizeof st);
        if(dfs(x,y,ex,ey))puts("YES");
        else puts("NO");
    }
    
    return 0;
}