样例和#1在本地能过,但提交就全wrong了
查看原帖
样例和#1在本地能过,但提交就全wrong了
1458676
juggernaut_485楼主2024/10/12 14:02
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 1005;
int T;
int g[N][N];
int dist[N][N];
PII q[N * N];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

bool bfs(int x1, int y1, int n){
    int hh = 0, tt = 0;
    dist[x1][y1] = 0;
    q[tt++] = {x1, y1};
    while(hh <= tt){
        PII t = q[hh++];
        for(int i = 0; i<4; i++){
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 1 || a > n || b < 1 || b > n) continue;
            if(dist[a][b] != -1) continue;
            if(dist[t.x][t.y] + 1 > g[a][b]) continue;
            q[tt++] = {a, b};
            dist[a][b] = dist[t.x][t.y] + 1;
            if(a == n && b == n) return true;
        }
    }
    return false;
}

int main(){
    scanf("%d", &T);
    while(T--){
        memset(g, 0x3f, sizeof g);
        memset(dist, -1 , sizeof dist);
        int n;
        scanf("%d",&n);
        if(n == 1){
            printf("YES\n");
            continue;
        }
        for(int i = 1; i<= 2*n - 2; i++){
            int x1, y1;
            scanf("%d %d",&x1, &y1);
            g[x1][y1] = min(g[x1][y1], i);
        }
        if(bfs(1,1,n)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

样例和#1在本地能过,但提交就全wrong了,求大佬帮忙调调QAQ

2024/10/12 14:02
加载中...