登录以参加训练计划

课件1

课件2

搜索模板

void dfs(int x,int y){
	if(x==1&&y==n){
		ans++;
		return ;
	}
	for(int i=0;i<8;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>0&&ny>0&&nx<=n&&ny<=n&&vis[nx][ny]==0&&mp[nx][ny]==0){
			vis[nx][ny]=1;
			dfs(nx,ny);
			vis[nx][ny]=0;
		}
	}
}

#include<bits/stdc++.h>
using namespace std;
int mp[101][101],vis[101][101],n,ans;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int sx,sy,ex,ey;
void dfs(int x,int y){
	if(x==ex&&y==ey){
		ans++;
		return ;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>=0&&ny>=0&&nx<n&&ny<n&&vis[nx][ny]==0&&mp[nx][ny]==0){
			vis[nx][ny]=1;
			dfs(nx,ny);
		}
	}
}
int main(){
	int k;
	cin>>k;
	while(k--){
		cin>>n;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				vis[i][j]=0;
				char v;
				cin>>v;
				if(v=='.') mp[i][j]=0;
				else mp[i][j]=1; 
			}
		}
		cin>>sx>>sy>>ex>>ey;
		if(mp[sx][sy]||mp[ex][ey]) {
			cout<<"NO\n";
            continue;
		}
		ans=0;
		vis[sx][sy]=1;
		dfs(sx,sy);
		if(ans>0) cout<<"YES\n";
		else cout<<"NO\n";
	}
	

    return 0;
}