P15058 [UOI 2023 II Stage] Rectangles are everywhere

Nostopathy · 2026-02-27 09:56:17 · 题解

个人感觉是题解里面比较好理解的。

由于我们的主人公有走 0.5 格的特异功能，所以矩形之间必须连通才有可能阻断他的道路。

考虑并查集，合并同时维护每个连通块四个方向的边界。

思考什么样的连通块会阻断道路，有以下四种：

• 同时连接房间的上边和左边；
• 同时连接房间的下边和右边；
• 同时连接房间的上边和下边；
• 同时连接房间的左边和右边；

以上都会将起点或终点隔离。

实现时注意这个坐标顺序，太烦了，浪费了我半小时的青春。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5005;
int n, m, k, l[N], r[N], u[N], d[N], fa[N];
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){
    x = find(x), y = find(y);
    if(x != y){
        fa[x] = y;
        l[y] = min(l[y], l[x]);
        r[y] = max(r[y], r[x]);
        u[y] = min(u[y], u[x]);
        d[y] = max(d[y], d[x]);
    }
}
bool connected(int x, int y){
    return max(l[x], l[y]) <= min(r[x], r[y]) && max(u[x], u[y]) <= min(d[x], d[y]);
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= k; ++ i){
        fa[i] = i;
        cin >> l[i] >> u[i] >> r[i] >> d[i];
    }
    for(int i = 1; i <= k; ++ i)
        for(int j = i + 1; j <= k; ++ j)
            if(connected(i, j))
                merge(i, j);
    for(int i = 1; i <= k; ++ i){
        if(fa[i] != i) continue;
        bool pl = (l[i] == 0), pr = (r[i] == n), pu = (u[i] == 0), pd = (d[i] == m);
        if((pl && pr) || (pu && pd) || (pl && pu) || (pr && pd))
            return cout << "NO", 0;
    }
    cout << "YES";

    return 0;
}