信奥赛CSP-J复赛集训（bfs专题-刷题题单及题解）（5）：洛谷P3395：路障

题目描述

B 君站在一个 $n\times n$ 的棋盘上。最开始，B君站在 $(1,1)$ 这个点，他要走到 $(n,n)$ 这个点。

B 君每秒可以向上下左右的某个方向移动一格，但是很不妙，C 君打算阻止 B 君的计划。

每秒结束的时刻，C 君 会在 $(x,y)$ 上摆一个路障。B 君不能走在路障上。

B 君拿到了 C 君准备在哪些点放置路障。所以现在你需要判断，B 君能否成功走到 $(n,n)$。

保证数据足够弱：也就是说，无需考虑“走到某处然后被一个路障砸死”的情况，因为答案不会出现此类情况。

输入格式

首先是一个正整数 $T$，表示数据组数。

对于每一组数据：

第一行，一个正整数 $n$。

接下来 $2n-2$ 行，每行两个正整数 $x$ 和 $y$，意义是在那一秒结束后，$(x,y)$ 将被摆上路障。

输出格式

对于每一组数据，输出 Yes 或 No，回答 B 君能否走到 $(n,n)$。

样例 #1

样例输入 #1

22
1 1
2 25
3 3
3 2
3 1
1 2
1 3
1 4
1 5
2 2

样例输出 #1

Yes
Yes

提示

样例解释：

以下 0 表示能走，x 表示不能走，B 表示 B 君现在的位置。从左往右表示时间。

Case 1:
0 0    0 0    0 B  (已经走到了)
B 0    x B    x 0

Case 2:
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 x 0 0    0 0 x 0 0    0 0 x 0 0
0 0 0 0 0    0 0 0 0 0    0 0 x 0 0    0 0 x 0 0
B 0 0 0 0    0 B 0 0 0    0 0 B 0 0    0 0 x B 0 ......(B君可以走到终点)

数据规模：

防止骗分，数据保证全部手造。

对于 $20\%$ 的数据，有 $n\le 3$。

对于 $60\%$ 的数据，有 $n\le 500$。

对于 $100\%$ 的数据，有 $n\le 1000$。

对于 $100\%$ 的数据，有 $T\le 10$。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
int T,n,x,y; 
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0}; 
//创建结构体：存储一个点的坐标 
struct point{int x,y;
}q[1000010],z[2000];//q数组用与广搜维护队列，z数组存放障碍点 
bool vis[1010][1010];//标记数组
bool f;//标记是否有结果//广搜
void bfs(){int head=1,tail=1,t=1;//t用于计时，当前是第1秒 q[head].x=1;//起点入队 q[head].y=1;vis[1][1]=1;//标记起点走过while(head<=tail){if(q[head].x==n && q[head].y==n){//判断是否到终点 f=1;//标记能出break;//退出循环 }for(int i=0;i<=3;i++){int nx=q[head].x+dx[i];int ny=q[head].y+dy[i];if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0){tail++;q[tail].x=nx;//新点入队 q[tail].y=ny;vis[nx][ny]=1;//标记新点 }}//1秒过后，放入障碍点vis[z[t].x][z[t].y]=1;t++;//模拟时间：下一秒head++;//队首出队 } } 
int main(){cin>>T;while(T--){cin>>n;//多组测试数据，一定要记得初始化数组和标记 memset(q,0,sizeof(q));memset(z,0,sizeof(z));memset(vis,0,sizeof(vis));f=0; //输入障碍点并存储到z数组中 for(int i=1;i<=2*n-2;i++){cin>>x>>y;z[i].x=x;//第i秒结束时所放路障的坐标 z[i].y=y; }//广搜 bfs(); //输出 if(f==1) cout<<"Yes"<<endl;else cout<<"No"<<endl; }return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容