20分求助
  • 板块P3395 路障
  • 楼主cubehead
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/7 11:00
  • 上次更新2023/11/3 11:13:54
查看原帖
20分求助
843733
cubehead楼主2023/7/7 11:00
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

struct Info {
    int x, y;
};
int T, n, ans[1001][1001], dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
bool vis[1001][1001];
queue<Info> q;

void bfs(int x, int y) {
    q.push({x, y});
    vis[x][y] = true;
    ans[x][y] = 0;
    while (q.size()) {
        int t1 = q.front().x, t2 = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = t1 + dx[i], yy = t2 + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && !vis[xx][yy]) {
                vis[xx][yy] = true;
                q.push({xx, yy});
                ans[xx][yy] = ans[t1][t2] + 1;
            }   
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        memset(ans, 0x3f, sizeof ans);
        ans[1][1] = 0;
        cin >> n;
        for (int i = 1; i <= 2 * n - 2; i++) {
            int x, y;
            cin >> x >> y;
            vis[x][y] = true;
        }
        bfs(1, 1);
        if (ans[n][n] == INF) 
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    return 0;
}
2023/7/7 11:00
加载中...