20分后面四个点一直蜜汁RE求助
  • 板块P3395 路障
  • 楼主焚魂
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/8/13 18:04
  • 上次更新2023/11/4 10:47:18
查看原帖
20分后面四个点一直蜜汁RE求助
206423
焚魂楼主2021/8/13 18:04
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int t;
int n;
int x[2010],y[2010];
int map[1010][1010];
bool v[1010][1010];
struct node{
    int x,y;
}q[10000010];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool flag = false;

void refresh() {
    memset(q,0,sizeof(q));
    memset(map,0,sizeof(map));
    memset(v,0,sizeof(v));
}

void bfs() {
    int head = 1,tail = 1;
    q[1].x = 1;
    q[1].y = 1;
    v[1][1] = true;
    while(head <= tail) {
        for(int i = 0;i <= 3;i++) {
            int xx = q[head].x + dx[i];
            int yy = q[head].y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > n || v[xx][yy] == true || map[xx][yy] == 1)
                continue;
            v[xx][yy] = true;
            tail ++;
            q[tail].x = xx;
            q[tail].y = yy;
            if(xx == n && yy == n) {
                flag = true;
                break;
            }
        }
        if(flag == true)
            break;
        map[x[head]][y[head]] = 1;
        head++;
    }
}

int main() {
    cin >> t;
    for(int k = 1;k <= t;k++) {
        cin >> n;
        for(int j = 1;j <= 2*n-2;j++) {
            cin >> x[j] >> y[j];
        }
        if(n == 1) {
            cout << "Yes" << endl;
            continue;
        }
        refresh();
        bfs();
        if(flag == true) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}
2021/8/13 18:04
加载中...