题目：
https://www.luogu.com.cn/problem/P3395
题目描述
B 君站在一个 n×n 的棋盘上。最开始，B君站在 (1,1) 这个点，他要走到(n,n) 这个点。
B 君每秒可以向上下左右的某个方向移动一格，但是很不妙，C 君打算阻止 B 君的计划。
每秒结束的时刻，C 君 会在 (x,y) 上摆一个路障。B 君不能走在路障上。
B 君拿到了 C 君准备在哪些点放置路障。所以现在你需要判断，B 君能否成功走到 (n,n)。
保证数据足够弱：也就是说，无需考虑“走到某处然后被一个路障砸死”的情况，因为答案不会出现此类情况。
输入格式
首先是一个正整数 T，表示数据组数。
对于每一组数据：
第一行，一个正整数 n。
接下来 2*n−2 行，每行两个正整数 x 和 y，意义是在那一秒结束后(x,y) 将被摆上路障。
输出格式
对于每一组数据，输出 Yes 或 No，回答 B 君能否走到 (n,n)。
奇妙思路：借鉴了洛谷 P10491陨石砸牧场，但是这题是先走路再放障碍物的，并且强调不会砸死。我不能理解不能砸死的情况（因为有这种可能），这题的障碍物放置的时间不能类似陨石那题，它要统一+1，因为是先走再放，我们模拟下，如果走一步为1秒，第2秒放置障碍物(不能是第一秒放)。走第二秒的时候才进行判断，1+1<2是不成立的，所以本就是不能走的。此外，在队列里取出队首数据，就可以将它出队列了。
代码如下：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;int dx[] = {1, 0, -1, 0}; // 方向数组
int dy[] = {0, -1, 0, 1};int T;
int n; // 地图大小（n x n）
int times[1005][1005]; // 储存路障出现时间点（0表示无路障）
int steps[1005][1005]; // 记录到达每个位置的最小步数（-1表示未访问）
bool res[1005]; // 储存每组测试用例的结果
struct Node{int x;int y;
};
queue<Node> q;bool bfs(int startX, int startY){Node start = {startX, startY};q.push(start);steps[startX][startY] = 0; // 起点步数为0while (!q.empty()) {Node currenthead = q.front();//取出当前队首数据 q.pop();//取出队首数据就可以出队了 int x = currenthead.x;int y = currenthead.y;if (x == n && y == n) {return true; // 到达终点}for (int k = 0; k < 4; k++) {int tx = x + dx[k];int ty = y + dy[k];if (tx >= 1 && tx <= n && ty >= 1 && ty <= n) // 基本检查边界{ if ((steps[x][y] + 1 < times[tx][ty] || times[tx][ty] == 0) && steps[tx][ty] == -1)//检查到达探索点的时间是否小于放置障碍物的时间，以及该点是否探索过。-1为探索过 {steps[tx][ty] = steps[x][y] + 1; Node newNode = {tx, ty};q.push(newNode);}}}}return false; // 无法到达终点
}int main()
{cin >> T;for (int i = 1; i <= T; i++){cin >> n;memset(times, 0, sizeof(times)); memset(steps, -1, sizeof(steps)); for (int i = 1; i <= 2 * n - 2; i++) { int x, y;cin >> x >> y;times[x][y] = i + 1; // 障碍物放置时间,这里i+1是因为我们想要的是第i步后放置的障碍物.}res[i] = bfs(1, 1); // 从(1,1)开始BFS，结果存入res数组}for (int i = 1; i <= T; i++){if (res[i])cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}
