迷宫
题目模型:DFS连通性模型
题目描述:
二维矩阵表示地图,每个格点有两种状态,$\.$ 和 $ \# $,前者表示可以通过后者不能。
给定A,B两点,问A能否到达B?
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n,T=1;
char q[N][N];
bool st[N][N];
int a,b,c,d;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
bool dfs(int x,int y)
{
// 能否走通
if(q[x][y]=='#') return false;
// 判断终点
if(x==c && y==d) return true;
// 标记,避免重复搜索
st[x][y]=true;
for(int i=0;i<4;i++){
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)) return true;
}
// 四个方向都不能通
return false;
}
int main()
{
cin>>T;
while(T--)
{
memset(st,0,sizeof st);
cin>>n;
for(int i=0;i<n;i++) cin>>q[i];
cin>>a>>b>>c>>d;
if(dfs(a,b)) puts("YES");
else puts("NO");
}
return 0;
}