太阳之华 连通块计数

C-太阳之华_牛客小白月赛89 (nowcoder.com)

思路：可以发现，最多经过一次操作就能知道结果：

• 全是蓝色：蓝方胜
• 全是红色：红方胜
• 红方经过一次操作：
  • 存在一个连通块扩散等于蓝色个数：红方胜
  • 否则，红蓝一直重复进行，平局

因此，对棋盘进行一次遍历，将所有红色连通块全部找出来并记上标记（类似并查集判定连通块）。之后再对每个连通块扩散吞食掉的蓝块进行计数，由于需要考虑一个连通块中不同红块对同一个蓝块的重复影响，这里用set进行去重。

之后对每个连通块扩散的蓝色个数进行判定即可得到答案。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int fx[] = {0, 0, 1, -1};
int fy[] = {1, -1, 0, 0};
void solve() {
    int n,m; cin>>n>>m;
    vector<string> ph(n);
    vector<vector<int>> rcd(n, vector<int>(m, 0));
    for(auto &t: ph) cin>>t;
    int cnt = 1;
    int cntb = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cntb += (ph[i][j] == '.');
        }
    }
    // 全蓝：蓝色胜利
    if(cntb == n * m) {
        cout<<"Blue\n";
        return ;
    }

    // 找到所有的红色联通块
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(rcd[i][j]) continue;
            if(ph[i][j] == '#') {
                auto dfs = [&](auto &&self, int x, int y, int id) -> void {
                    rcd[x][y] = id;
                    for(int i = 0; i < 4; ++i) {
                        int xx = x + fx[i], yy = y + fy[i];
                        if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
                        if(rcd[xx][yy] || ph[xx][yy] == '.') continue;
                        self(self, xx, yy, id);
                    }
                };
                dfs(dfs, i, j, cnt++);
            }
        }
    }

    // 记录每个红色联通块周围的蓝块数
    set<pair<int,int>> se[cnt];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(ph[i][j] == '.') continue;
            for(int k = 0; k < 4; ++k) {
                int x = i + fx[k], y = j + fy[k];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(ph[x][y] == '.') se[rcd[i][j]].insert({x, y});
            }
        }
    }

    // 红色联通块周围的蓝色块数等于总蓝色块数：红色胜利
    for(int i = 1; i < cnt; ++i) {
        if(se[i].size() == cntb) {
            cout<<"Red\n";
            return ;
        }
    }
    // 否则，将会一直重复进行，平局
    cout<<"Draw\n";
}
int main()
{
    int t; cin>>t;
    while(t--) {
        solve();
    }
}