题解 | 太阳之华 | 洪水

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
bitset<N> mat[N];
bool vis[N][N];
int cnt,tot;
int n,m;
array<int, 2> stk[N*N];
int tp;
int dir[5] = {1, 0, -1, 0, 1};

void clear(){
    while(tp) {
        auto [x, y] = stk[tp--];
        if(mat[x][y] == 0) {
            vis[x][y] = false;
            cnt--;
        }
    }
}

void dfs(int i, int j) {
    if(i < 1 || j < 1 || i > n || j > m) return;
    if(vis[i][j]) return;
    vis[i][j] = true;
    stk[++tp] = {i, j};
    if(mat[i][j] == 0) {
        cnt++;
        return;
    }
    for(int d = 0; d < 4; d++) {
        dfs(i + dir[d],j + dir[d + 1]);
    }
}

void solve(){
    bool ok = false;
    cin >> n >> m;
    cnt = tot = 0;
    for(int i = 1; i <= n ; i++ ){
        // mat[i].reset();
        for(int j = 1; j <= m ; j++ ){
            vis[i][j] = false;
            char c;
            cin >> c;
            if(c == '#') mat[i][j] = true, ok = true; 
            else mat[i][j] = false, tot++;
        }
    }
    if(!ok){
        cout << "Blue" << "\n";
        return;
    }
    ok=true;
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1; j <= m; j++) {
            if(mat[i][j] && !vis[i][j]) {
                dfs(i,j);
                ok &= cnt < tot;
                clear();
            }
        }
    }
    if(ok) {
        cout << "Draw" << "\n";
    } else {
        cout << "Red" << "\n";
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();    
}
// 64 位输出请用 printf("%lld")