https://www.luogu.org/problem/show?pid=3395
题目背景
此题约为NOIP提高组Day1T1难度。
题目描述
B君站在一个n*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<=3
。
对于60%
的数据,有n<=500
。
对于100%
的数据,有n<=1000
。
对于100%
的数据,有T<=10
。
BFS
#include <cstring>
#include <cstdio>
#include <queue> #define min(a,b) (a<b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int N();
int n,tim[N][N];
struct Node {
int x,y,t;
}u,v;
std::queue<Node>que;
int fx[]={,,,-};
int fy[]={,,-,};
bool vis[N][N]; int Presist()
{
int t; read(t);
for(bool flag; t--; )
{
read(n); flag=;
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
tim[i][j]=0x3f3f3f3f;
for(int x,y,i=; i<=n-<<; ++i)
read(x),read(y),tim[x][y]=min(i,tim[x][y]);
for(; !que.empty(); ) que.pop();
memset(vis,,sizeof(vis));
u.x=u.y=; u.t=;
vis[][]=; que.push(u);
for(; !que.empty(); )
{
u=que.front(); que.pop();
if(u.x==n&&u.y==n) {flag=;break;}
for(int i=; i<; ++i)
{
v.x=u.x+fx[i],v.y=u.y+fy[i],v.t=u.t+;
if(v.x<||v.y<||v.x>n||v.y>n) continue;
if(v.t>tim[v.x][v.y]||vis[v.x][v.y]) continue;
vis[v.x][v.y]=; que.push(v);
}
}
if(flag) puts("Yes"); else puts("No");
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}