自动搬运

查看原文

来自洛谷，原作者为

	Invisible_Blade **

搬运于2025-08-24 21:48:32，当前版本为作者最后更新于2019-08-29 21:40:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先的一点是：

由于数据有T组，所以每次计算完后要重置所有用过的数据。

用结构体手写队列，加上广搜，每秒广搜完所有可能走过的地方后，再放路障。

以下的代码是定义数据的代码。

int T,n,x,y,nx,ny,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct q{
	int x,y;
}que[10000010],no[1001];
bool pd[1001][1001];

在上面的代码里，T是要处理的T组数据，n是棋盘大小，x，y是输入路障的坐标，nx，ny是待会广搜要用到的下一步走到的坐标，dx与dy是方向数组。 在结构体里面，que数组是用来广搜的，no数组是来存放路障的，no[i]代表第i秒结束时放路障的坐标。

下面的代码是主函数。

int main(){
	scanf("%d",&T);
	for(int e=1;e<=T;e++){
		scanf("%d",&n);
		for(int i=1;i<=2*n-2;i++){
			scanf("%d %d",&x,&y);
			no[i].x=x,no[i].y=y;
		}
		bfs();
		reset();
	}
	return 0;
}

bfs是广搜，输出此组数据能否到达。reset是重置函数。

以下是重置函数。

void reset(){
	memset(que,0,sizeof(que));
	memset(pd,0,sizeof(pd));
	memset(no,0,sizeof(no));
}

接下来重头戏，精华！！！！！广搜怎摸写？

void bfs(){
	int t=1,head=1,tail=2;
	que[head].x=1,que[head].y=1,pd[1][1]=1;
	do{
		for(int i=0;i<4;i++){
			nx=que[head].x+dx[i];
			ny=que[head].y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&pd[nx][ny]==0){
				que[tail].x=nx;
				que[tail].y=ny;
				tail++;
				pd[nx][ny]=1;
			}
		}
		pd[no[t].x][no[t].y]=1;
		t++;
		head++;
	}while(head<tail);
	for(int i=tail;i>=1;i--){
		if(que[i].x==n&&que[i].y==n){
			printf("Yes\n");
			return;
		}
	}
	printf("No\n");
	return;
}

在这里t是记录第t秒的，配合no数组，head是头指针，tail是尾指针。 先把que[head].x与.y标记为（1，1），pd[1][1]=1为（1，1）走过了。 do while循环里，for循环为4个方向，nx，ny为下一个走向，如果符合条件那么把他存到尾指针，tail++，把他标记为走过。 当这个head四个方向都判断完后，也就是这一秒走过后，用pd[no[t].x][no[i].y]=1来放路障，标记为1相当于不能走了。 do while 外的for循环为在que数组中找有没有到达（n，n）的点，如果有，输出Yes换行return，循环完毕说明没有到达，就输出No换行return。

所以完整代码如下：

#include<bits/stdc++.h>
using namespace std;
int T,n,x,y,nx,ny,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct q{
	int x,y;
}que[10000010],no[1001];
bool pd[1001][1001];
void bfs(){
	int t=1,head=1,tail=2;
	que[head].x=1,que[head].y=1,pd[1][1]=1;
	do{
		for(int i=0;i<4;i++){
			nx=que[head].x+dx[i];
			ny=que[head].y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&pd[nx][ny]==0){
				que[tail].x=nx;
				que[tail].y=ny;
				tail++;
				pd[nx][ny]=1;
			}
		}
		pd[no[t].x][no[t].y]=1;
		t++;
		head++;
	}while(head<tail);
	for(int i=tail;i>=1;i--){
		if(que[i].x==n&&que[i].y==n){
			printf("Yes\n");
			return;
		}
	}
	printf("No\n");
	return;
}
void reset(){
	memset(que,0,sizeof(que));
	memset(pd,0,sizeof(pd));
	memset(no,0,sizeof(no));
}
int main(){
	scanf("%d",&T);
	for(int e=1;e<=T;e++){
		scanf("%d",&n);
		for(int i=1;i<=2*n-2;i++){
			scanf("%d %d",&x,&y);
			no[i].x=x,no[i].y=y;
		}
		bfs();
		reset();
	}
	return 0;
}

禁止抄袭！！！看我写题解这么辛苦的份上给个赞吧~~~