哈尔滨理工大学软件与微电子学院程序设计竞赛——H.Maze【BFS 并查集】

题目传送门

题解

• 不考虑 $Q$ 次询问的话，就是简单的 $BFS$
• 那么有了 $Q$ 次询问，那么直接使用 $并查集$ 维护即可
• 注意数组大小

AC-Code

#include <bits/stdc++.h>
using namespace std;const int maxn = 3e3 + 7;
int N, M, Q;
struct NODE {
    int x, y;NODE(int x = 0, int y = 0) :x(x), y(y) {
    }
};
char mp[maxn][maxn];
bool vis[maxn][maxn];
int dx[] = {
     0,0,1,-1 };
int dy[] = {
     1,-1,0,0 };
int getId(int x, int y) {
    return x * M + y;
}
struct UFS {
    int f[maxn * maxn];unsigned int rank[maxn * maxn];UFS() {
    }void init() {
    for (int i = 0; i < maxn * maxn; ++i) {
    f[i] = i;	rank[i] = 0;}}int getF(int x) {
    return f[x] == x ? x : (f[x] = getF(f[x]));}void merge(int x, int y) {
    x = getF(x), y = getF(y);if (x == y)	return;if (rank[x] < rank[y])	f[x] = y;else	f[y] = x;if (rank[x] == rank[y])	++rank[x]; // 走else合并}bool isUnion(int x, int y) {
    return getF(x) == getF(y);}
}UF;
bool judge(int x, int y, int nx, int ny) {
    if (nx < 0 || nx >= N || ny < 0 || ny >= M)	return false;if (mp[x][y] == mp[nx][ny])	return false;return !vis[nx][ny];
}
void bfs(NODE start) {
    queue<NODE>q;q.push(start);vis[start.x][start.y] = true;while (!q.empty()) {
    NODE now = q.front();q.pop();for (int i = 0; i < 4; ++i) {
    int nx = now.x + dx[i];int ny = now.y + dy[i];if (judge(now.x, now.y, nx, ny)) {
    q.push(NODE(nx, ny));vis[nx][ny] = true;UF.merge(getId(nx, ny), getId(now.x, now.y));}}}
}
int ans[maxn * maxn];
int main() {
    while (cin >> N >> M >> Q) {
    memset(ans, 0, sizeof(ans));memset(vis, false, sizeof(vis));UF.init();for (int i = 0; i < N; ++i)for (int j = 0; j < M; ++j)cin >> mp[i][j];for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
    if (UF.getF(getId(i, j)) == getId(i, j)) {
    bfs(NODE(i, j));}}}for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
    ++ans[UF.getF(getId(i, j))];}}for (int i = 0; i < Q; ++i) {
    int x, y;	cin >> x >> y;cout << ans[UF.getF(getId(x - 1, y - 1))] << endl;}}
}