20分代码求助,样例输出“No No”
  • 板块P3395 路障
  • 楼主SSTFXJQ
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/2 19:23
  • 上次更新2023/11/2 21:01:40
查看原帖
20分代码求助,样例输出“No No”
837043
SSTFXJQ楼主2023/11/2 19:23
#include<iostream>
#include<queue>
using namespace std;
int dis[1005][1005],z[1005][1005],used[1005][1005];
int t,n,a,b,s;
int dx[5]={0,0,-1,1}; //上下左右移动 1 格  
int dy[5]={1,-1,0,0};
struct node{
	int x1,y1,t1;
};
void bfs(int t){
	s=0;
	for(int i=1;i<=n;i++){  //初始化 
		for(int j=1;j<=n;j++){
			if(i==1&&j==1)dis[i][j]=0;
			else dis[i][j]=1e9;
		}
	}
	queue<node>q;
	q.push({1,1,0});
	while(q.size()){
		int x=q.front().x1,y=q.front().y1,t=q.front().t1;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i],nt=t+1;
			if(nx>n||nx<1||ny>n||ny<1)continue;
			if(z[nx][ny]==nt||used[nx][ny])continue;
			if(dis[x][y]+1<dis[nx][ny]){
				used[nx][ny]=1;
				dis[nx][ny]=dis[x][y]+1;
				q.push({nx,ny,nt});
			}
		} 
	}
}
int main(){
	int xx,yy;
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n;
		for(int j=1;j<=2*n-2;j++){  //输入障碍 
			cin>>xx>>yy;
			z[xx][yy]=j;    //存 点变路障的时间 
		}
		used[1][1]=1;
		bfs(0);
		if(dis[n][n]==1e9)cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	
	return 0;
} 

愿有大佬解答,Thanks♪(・ω・)ノ_

2023/11/2 19:23
加载中...