这道题是一道简单的BFS的题。
我们注意到这道题最不一样的地方是：每秒结束的时刻，C君会在\((x,y)\)上摆一个路障。B君不能走在路障上。
定义一个\(vis\)数组（bfs基本做法），将没有走过的点\(vis[x][y]\)设置为\(0\)，将走过的点\(vis[x][y]\)设置为\(1\)，将不能走的点\(vis[x][y]\)设置为\(-1\)。
每秒走一步，所以我们要在B君每走一步之后将某个\(vis[x][y]\)设置为\(-1\)。我们要将这些点的坐标全部保存下来。
题目中说了数据足够弱，我们可以不考虑B君“被砸死”的情况（实在是太幸运了）。
输入：
每个点都有\(xy\)这两个数据，也可以分开存，但我们这里使用一个结构体存储。
const int dx[5]={0,1,0,-1,0}, dy[5]={0,0,1,0,-1};//可以遍历这两个数组实现移动
struct JF{int x, y;
} quexy[maxn * maxn], bre[maxn * 2];//quexy是bfs的队列 bre存的是路障的坐标
int T, n, seconds=0, mapp[maxn][maxn];//second用来记录秒数，便于取出bre中的数据。mapp用来记录图的状态。
还有，由于是T组数据，我们在输入时要注意重新初始化。
inline void init(){ //输入cin >> n;seconds = 0; //初始化for (int i = 1;i <= maxn;i ++) bre[i].x = bre[i].y = 0;//初始化for (int i = 1;i <= 2 * n - 2;i ++)cin >> bre[i].x >> bre[i].y; //输入路障坐标for (int i = 1;i <= n;i ++)for (int j = 1;j <= n;j ++)mapp[i][j] = 0; //初始化return ;
}
搜索：
void bfs(){quexy[1].x = 1;quexy[1].y = 1; //起点入队（起点为(1,1)）int head = 0, tail = 1; //两个指针，分别指向队首和队尾while (head < tail){ //head = tail时说明搜完了head ++; //每次都要以一个为起点向上下左右搜索，将这个移除队列，等价于让head指针后移一个seconds ++; //记录秒数for (int i = 1;i <= 4;i ++){ //四个方向int xx = quexy[head].x + dx[i];int yy = quexy[head].y + dy[i]; //xx yy存储走了一步之后的坐标if ((xx > 0 && xx <= n) && (yy > 0 && yy <= n) && mapp[xx][yy] == 0){//前两个()中的内容用来判断是否越界（是否走出了地图)//而且当且仅当这个地方我们没有走过时，我们才有必要走tail ++; //将这个符合要求的点入队，队尾指针当然要后移mapp[xx][yy] = 1;//更改状态为走到了quexy[tail].x = xx;quexy[tail].y = yy;//坐标入队}}if (mapp[bre[seconds].x][bre[seconds].y] != 1) mapp[bre[seconds].x][bre[seconds].y] = -1;//不用考虑被砸死的情况，而且走过的地方我们也没必要改}return ;
}
输出：
inline void fprint(){if (mapp[n][n] == 1){cout << "Yes" << '\n';return ;}cout << "No" << '\n';return ;
}
完整代码：
#include <iostream>
using namespace std;
const int maxn = 1e3 + 5;
const int dx[5]={0,1,0,-1,0}, dy[5]={0,0,1,0,-1};
struct JF{int x, y;
} quexy[maxn * maxn], bre[maxn * 2];
int T, n, seconds=0, mapp[maxn][maxn];
inline void init(){cin >> n;seconds = 0; for (int i = 1;i <= maxn;i ++) bre[i].x = bre[i].y = 0;for (int i = 1;i <= 2 * n - 2;i ++)cin >> bre[i].x >> bre[i].y;for (int i = 1;i <= n;i ++)for (int j = 1;j <= n;j ++)mapp[i][j] = 0; return ;
}
void bfs(){quexy[1].x = 1;quexy[1].y = 1;int head = 0, tail = 1;while (head < tail){head ++;seconds ++;for (int i = 1;i <= 4;i ++){int xx = quexy[head].x + dx[i];int yy = quexy[head].y + dy[i];if ((xx > 0 && xx <= n) && (yy > 0 && yy <= n) && mapp[xx][yy] == 0){tail ++;mapp[xx][yy] = 1;quexy[tail].x = xx;quexy[tail].y = yy;}}if (mapp[bre[seconds].x][bre[seconds].y] != 1) mapp[bre[seconds].x][bre[seconds].y] = -1;state();}return ;
}
inline void fprint(){if (mapp[n][n] == 1){cout << "Yes" << '\n';return ;}cout << "No" << '\n';return ;
}
int main(){cin >> T;while (T --){init();bfs();fprint();}return 0;
}