红色涂格(Red Painting) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H, W, Q;
    if (!(cin >> H >> W >> Q)) return 0;
    int tot = H * W;
    vector<int> p(tot);
    vector<char> red(tot, 0);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int x) {
        while (p[x] != x) x = p[x] = p[p[x]];
        return x;
    };
    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int r, c;
            cin >> r >> c;
            --r; --c;
            int u = r * W + c;
            red[u] = 1;
            for (int d = 0; d < 4; ++d) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                    int v = nr * W + nc;
                    if (red[v]) p[find(u)] = find(v);
                }
            }
        } else {
            int ra, ca, rb, cb;
            cin >> ra >> ca >> rb >> cb;
            --ra; --ca; --rb; --cb;
            int u = ra * W + ca, v = rb * W + cb;
            if (red[u] && red[v] && find(u) == find(v)) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}