dfs 20分 1AC+2RE+2TLE 求助大佬!!
  • 板块P3395 路障
  • 楼主YangjinRun
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/8/22 13:06
  • 上次更新2023/10/27 14:11:54
查看原帖
dfs 20分 1AC+2RE+2TLE 求助大佬!!
666311
YangjinRun楼主2022/8/22 13:06
#include<bits/stdc++.h>
using namespace std;
int t,n,a[1010],b[1010],flag[1010][1010],k,h[4]={-1,1,0,0},l[4]={0,0,-1,1};
bool f;
void dfs(int x,int y){
	if(x==n && y==n){
		f=true;
		return;
	}
	for(int i=0;i<4;i++){
		int xx=x+h[i];
		int yy=y+l[i];
		if(flag[xx][yy]==0 && xx>=1 && xx<=n && yy>=1 && yy<=n){
			k+=1;
			flag[xx][yy]=1;
			flag[a[k]][b[k]]=1;
			dfs(xx,yy);
			flag[xx][yy]=0;
			flag[a[k]][b[k]]=0;
			k-=1;
		}
	}
	return;
}
int main(){
	cin>>t;
	while(t--){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(flag,0,sizeof(flag));
		f=false;
		k=0;
		cin>>n;
		for(int i=1;i<=2*n-2;i++) cin>>a[i]>>b[i];
		dfs(1,1);
		if(f==true) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}
2022/8/22 13:06
加载中...