题目连接:牛客5278 J 能到达吗node
给定一个 \(n\times m\) 的地图,地图的左上角为 \((1, 1)\) ,右下角为 \((n,m)\)。
地图上有 \(k\) 个障碍物,你能够上下左右走地图,可是不能走出地图或走到障碍物上。
计算无序对 \(\{ (x_i,y_i), (x_j,y_j) \}\) 知足两点相互可达的对数。
答案对 \(10^9 + 7\) 取模,多组数据。
数据范围: \(1 \le T\le 10^4, 1\le n, m\le 2\times 10^5, 0\le k\le 10^6\)。
数据保证不存在同一位置的障碍物,而且 \(\sum k \le 10^6\)。c++
https://ac.nowcoder.com/discuss/411541?type=101&order=0&pos=4&page=0git
// Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define rint register int #define rep(i, l, r) for (rint i = l; i <= r; i++) #define per(i, l, r) for (rint i = l; i >= r; i--) #define mset(s, _) memset(s, _, sizeof(s)) #define pb push_back #define pii pair <int, int> #define mp(a, b) make_pair(a, b) inline int read() { int x = 0, neg = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(int x) { if (x < 0) { putchar('-'); x = -x; } if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } const int N = 2000001; struct node { int x, y; friend bool operator < (const node &a, const node &b) { if (a.x != b.x) return a.x < b.x; else return a.y < b.y; } } a[N]; int f[N]; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } void Union(int x, int y) { x = find(x), y = find(y); if (sz[x] > sz[y]) { // 小的合并到大的上面 fa[y] = x; sz[x] += sz[y]; } else { fa[x] = y; sz[y] += sz[x]; } } void add_row() { lists[++row].clear(); } void add_line(int l, int r, ll s) { col++; fa[col] = col, sz[col] = s; lists[row].pb({l, r, col}); } int main() { for (int _ = read(); _; _--) { n = read(), m = read(), k = read(); for (int i = 1; i <= k; i++) { a[i].x = read(), a[i].y = read(); } sort(a + 1, a + k + 1); if (k == 0) { add_row(); } } }