题目背景：
此题约为NOIP提高组Day1T1难度。
题目描述：
B君站在一个n×nn\times nn×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)。
样例输入：
2
2
1 1
2 2
5
3 3
3 2
3 1
1 2
1 3
1 4
1 5
2 2
样例输出：
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。
AC Code：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define N 2020 int n,k,map[N][N],a[N],b[N];//map数组是地图，a和b数组是障碍坐标 bool vis[N][N],flag;//vis是标记数组，flag标记变量记录是否能走到(n,n) int dx[]={0,0,1,-1};//两个方向数组 int dy[]={1,-1,0,0}; struct node { int x,y,t; }; queue<node> q;//这里采用C++ STL的队列 bool judge(int x,int y) { //不越界 and 这个点不是障碍物 and这个点没有走过 if(x>=1&&x<=n&&y>=1&&y<=n&&map[x][y]==0&&vis[x][y]==false) { return true; } return false; } void bfs(int x,int y,int t) { node now,next; now.x=x; now.y=y; now.t=t; q.push(now);//起点入队 while(!q.empty()) {//循环保证队列不为空 now=q.front();//取出队首元素 q.pop();//弹出队首 if(now.x==n&&now.y==n) {//走到(n,n) flag=true;//flag修改为true return ;//直接返回 } //在那一秒结束后，(x,y)将被摆上路障，所以这里应该是相应的时间-1 map[a[now.t-1]][b[now.t-1]]=1; for(int i=0;i<4;i++) {//四个方向搜索 int tx=now.x+dx[i]; int ty=now.y+dy[i]; if(judge(tx,ty)) {//合法判断 vis[tx][ty]=true;//标记该点 next.x=tx; next.y=ty; next.t=now.t+1;//时间+1 q.push(next);//入队 } } } } int main() { scanf("%d",&k); while(k--) { scanf("%d",&n); for(int i=1;i<=2*n-2;i++) { scanf("%d %d",&a[i],&b[i]); } flag=false; memset(vis,false,sizeof(vis));//标记数组清零 memset(map,0,sizeof(map));//地图全部初始化为0 vis[1][1]=true;//标记起点 bfs(1,1,0); if(flag) {//到达(n,n) printf("Yes\n"); }else {//无法到达 printf("No\n"); } } return 0; }
