也对java不友好, 最后两个案例mle了
然后换c++,过了
贴代码
```c++
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e3 + 10, INF = 0x3f3f3f3f;
PII q[N * N];
int barrier[N][N];
int dist[N][N];
int n;
int hh, tt;
int x, y, t;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool bfs() {
hh = 0;
tt = -1;
q[++tt] = {1, 1};
dist[0][0] = 0;
if (n == 1) return true;
while (hh <= tt) {
auto t = q[hh++];
if (dist[t.x][t.y] + 1 > barrier[n][n]) return false;
for (int i = 0; i < 4; i++) {
int x = t.x + dx[i], y = t.y + dy[i];
if (x < 1 || x > n || y < 1 || y > n) continue;
if (dist[x][y] >= 0) continue;
if (dist[t.x][t.y] + 1 > barrier[x][y]) continue;
dist[x][y] = dist[t.x][t.y] + 1;
q[++tt] = {x, y};
if (x == n && y == n) return true;
}
}
return false;
}
int main() {
scanf("%d", &t);
while (t-- > 0) {
scanf("%d", &n);
memset(dist, -1, sizeof dist);
memset(barrier, 0x3f, sizeof barrier);
for (int i = 1; i <= 2 * n - 2; i++) {
scanf("%d %d", &x, &y);
barrier[x][y] = min(barrier[x][y], i);
}
if (bfs()) printf("Yes\n");
else printf("No\n");
}
return 0;
}
```
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
/**
* 输出流, 输出完之后记得用 out.flush() 清空一下缓存区
*/
static PrintWriter out = new PrintWriter(System.out);
/**
* FastReader类 参数-readAheadLimit: 一行可读取的最大字符数量, 根据题目的实际情况修改[默认(int) (1e6 + 10)]
*/
static FastReader sc = new FastReader((int) (1e6 + 10));
///////////////////////////////////////////////
////////////////////静态变量///////////////////////////
static final int N = (int) 1e3 + 10, INF = 0x3f3f3f3f;
// static int arr[] = new int[N];
// static int q[] = new int[N];
static int barrier[][] = new int[N][N];
static int dist[][] = new int[N][N];
// static boolean st[][] = new boolean[N][N];
static int n, m, t;
static int res, ans;
///////////////////////////////////////////////
////////////////////静态方法///////////////////////////
///////////////////////////////////////////////
static void solve() {
while (sc.hasNext()) {
out.flush();
}
out.flush();
}
///////////////////////////////////////////////
///////////////////////////////////////////////
//////////////////写解决方法/////////////////////////////
static void solveCom() { // 不需要 hasNext()
int n = sc.nextInt();
out.flush();
}
static class Node {
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
static int hh, tt, x, y;
static Node q[] = new Node[N * N];
static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
static boolean bfs() {
tt = -1;
hh = 0;
q[++tt] = new Node(1, 1);
dist[1][1] = 0;
if (n == 1) return true;
while (hh <= tt) {
Node t = q[hh++];
if (dist[t.x][t.y] + 1 > barrier[n][n]) return false;
for (int i = 0; i < 4; i++) {
x = t.x + dx[i];
y = t.y + dy[i];
if (x < 1 || x > n || y < 1 || y > n) continue;
if (dist[x][y] >= 0) continue;
if (dist[t.x][t.y] + 1 > barrier[x][y]) continue;
dist[x][y] = dist[t.x][t.y] + 1;
q[++tt] = new Node(x, y);
if (x == n && y == n) return true;
}
}
return false;
}
/*
2
2
1 1
2 2
5
3 3
3 2
3 1
1 2
1 3
1 4
1 5
2 2
*/
static void solveSub() { // t 次
int t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
for (int i = 0; i < N; i++) {
Arrays.fill(barrier[i], INF);
Arrays.fill(dist[i], -1);
}
for (int i = 1; i <= 2 * n - 2; i++) {
x = sc.nextInt();
y = sc.nextInt();
barrier[x][y] = Math.min(barrier[x][y], i);
// for (int j = 0; j < 4; j++) {
// int a = x + dx[j], b = y + dy[j];
// if (a < 1 || a > n || b < 1 || b > n) continue;
// barrier[a][b] = Math.min(barrier[a][b], i);
// }
}
if (bfs()) out.println("Yes");
else out.println("No");
out.flush();
}
out.flush();
}
static void solveScan() { // 需要 hasNext()
solve();
out.flush();
}
///////////////////////////////////////////////
///////////////////////////////////////////////
public static void main(String[] args) throws Exception {
/* 调用solve方法,好处是有多个题解可以写n个solve方法 */
// solveCom();
solveSub();
// solveScan();
// 最后清空并关闭输出流
out.flush();
out.close();
}
///////////////////////////////////////////////
//////////////////////封装快速读取类的方法(基于Scanner的方法来写)/////////////////////////
static class FastReader { // 输入类
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int readLimit = (int) (1e6 + 10);
public FastReader(int readLimit) { this.readLimit = readLimit; }
public FastReader() { }
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
boolean hasNext() {
if (st != null && st.hasMoreTokens()) return true;
try {
br.mark(readLimit);
String line = br.readLine();
// 是如果当前行 无输入 直接回车, 是不会报错, 可以一直回车, 直到 当前行不为空字符串 为止
if (line == null || "".equals(line)) return false;
br.reset();
} catch (IOException e) {
return false;
}
return true;
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
double nextDouble() { return Double.parseDouble(next()); }
String nextLine() {
String line = null;
try {
line = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return line;
}
}
///////////////////////////////////////////////
}
```
by SadlerCS @ 2023-04-17 15:42:02