[AtCoder] [經典競程 90 題] 012 - Red Painting(★4)
題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_l
題目大意:
給定一個 $N \times M$ 的網格上,現在有兩種可能的操作,其中一種
詢問的時候等價問兩個點是不是在同個連通塊裡,所以弄個併查集每次塗色的時候都更新一下當前的連通資訊就好了。
題目大意:
給定一個 $N \times M$ 的網格上,現在有兩種可能的操作,其中一種
1 x y
代表把 ($x$, $y$) 塗成紅色的;另外一種 2 p q r s
代表詢問 ($p$, $q$) 可否只透過紅色的格子上下左右移動到 ($r$, $s$)。
詢問的時候等價問兩個點是不是在同個連通塊裡,所以弄個併查集每次塗色的時候都更新一下當前的連通資訊就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5;
class DSU {
private:
vector<int> p;
public:
void init(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int query(int x) {
if (p[x] != x) p[x] = query(p[x]);
return p[x];
}
void merge(int x, int y) {
p[query(x)] = query(y);
}
} dsu;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
bool a[N][N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
dsu.init(n * m);
auto Idx = [&m](int i, int j){
return i * m + j;
};
int q; cin >> q;
while (q--) {
int op; cin >> op;
if (op == 1) {
int x, y; cin >> x >> y;
a[--x][--y] = true;
for (int dt = 0; dt < 4; ++dt) {
int nx = x + dx[dt], ny = y + dy[dt];
if (0 > nx or nx >= n) continue;
if (0 > ny or ny >= m) continue;
if (a[nx][ny]) dsu.merge(Idx(x, y), Idx(nx, ny));
}
} else {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1, --x2, --y2;
cout << ((a[x1][y1] and a[x2][y2] and dsu.query(Idx(x1, y1)) == dsu.query(Idx(x2, y2))) ? "Yes" : "No") << '\n';
}
}
return 0;
}
留言
張貼留言