路障
题目描述
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
2
2
1 1
2 2
5
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\le3$。
对于 $60\%$ 的数据,有 $n\le500$。
对于 $100\%$ 的数据,有 $n\le1000$。
对于 $100\%$ 的数据,有 $T\le10$。
算法1
(BFS)
0.避雷点
1.路障的设置:“每秒结束的时刻” - B君走完一步之后,放路障
mp[zx[tmp.t-1]][zy[tmp.t-1]]; !time是从0开始的
2.路障的个数——题目给出的2*n-1个
3.数据开大点——不知道为什么开const int N = 1005
会wa,但是2005
就通过了
1.思路
1.一些数据的定义
用一个数组来存放路障的坐标 —— int zx[N],zy[N];
放路障之后的地图 —— int mp[N][N];
访问情况 —— bool vis[N][N];
能否到达终点 —— bool flag;
其他的BFS时需要的
2.初始化
每一组测试数据需要初始化成 0
1)memset(mp,0,sizeof(mp);
2)memset(vis,0,sizeof(vis);
3)flag = 0;
3.BFS 实现
1.当前点的坐标是否在边界内
2.当前点的访问情况
3.当前点有无障碍
4.提前结束条件为到达终点
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int T,n;
int mp[N][N]; //放障碍之后的地图
int zx[N],zy[N];//障碍的坐标
bool flag; //是否能走到终点
bool vis[N][N]; //访问情况
struct Point {
int x, y, t;
};
queue<Point>q; //bfs是由队列实现的
int dx[4]= {-1,0,1,0},dy[4]= {0,-1,0,1}; //偏移量
void bfs(Point op) {
q.push(op); //把初始状态放到队列里
vis[op.x][op.y]=1; //起始点+1,也就是以后不会再访问了
while(!q.empty()) {
auto tmp = q.front(); //去除队头
q.pop(); //出列
//设障碍
if(tmp.x==n&&tmp.y==n) {
flag = 1;
break; //提前结束
}
mp[zx[tmp.t-1]][zy[tmp.t-1]] = 1;
for(int i=0; i<4; i++) {
int a = tmp.x + dx[i],b = tmp.y + dy[i],c = tmp.t;
//如果我要访问的点
//1.下标越界情况 2.之前没有访问过 3.当前点没有障碍
if(a<1||a>n || b<1||b>n || vis[a][b]||mp[a][b]) continue;
vis[a][b]=1;
q.push({a,b,c+1});
}
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main() {
cin>>T;
while(T--) {
//每测试组要进行初始化
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
flag=0;
cin>>n;
//输入障碍坐标
for(int i=1; i<=2*n-2; i++) {
cin>>zx[i]>>zy[i];
}
Point p;
p.x=1, p.y=1, p.t=0;
bfs(p);
}
return 0;
}