题解 | 太阳之华

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=2e3+5;
vector<vector<char>>g;
vector<vector<bool>>vis;
using PII=pair<ll,ll>;
ll n,m;
ll cnt_r,cnt_l;
ll dx[]={0,0,1,-1};
ll dy[]={1,-1,0,0};

ll bfs(ll i,ll j){
    queue<PII>q;
    q.push({i,j});
    ll cmp=0;
    set<PII>s;

    while(!q.empty()){
        auto t=q.front();
        q.pop();

        ll x=t.first,y=t.second;
        for(ll k=0;k<4;k++){
            ll xt=x+dx[k],yt=y+dy[k];
            if(xt<1||xt>n||yt<1||yt>m||vis[xt][yt]==true)continue;
            if(g[xt][yt]=='.'){
                if(s.find({xt,yt})==s.end()){
                    cmp++;
                    s.insert({xt,yt});
                }
                continue;
            }
            vis[xt][yt]=true;
            q.push({xt,yt});
        }
    }
    
    return cmp;
}


int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll T;
    cin>>T;
    while(T--){
        cnt_r=0;
        cnt_l=0;
        cin>>n>>m;
        g.assign(n+1,vector<char>(m+1));
        vis.assign(n+1,vector<bool>(m+1,false));
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++){
                cin>>g[i][j];
                if(g[i][j]=='#')cnt_r++;
                else cnt_l++;
            }
        }
        if(cnt_r==0){
            cout<<"Blue\n";
            continue;
        }
        bool f=0;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++){
                if(vis[i][j]==false&&g[i][j]=='#'){
                    vis[i][j]=true;
                    if(bfs(i,j)==cnt_l){
                        f=1;
                        break;
                    }
                }
            }
            if(f==1)break;
        }
        if(f==1){
            cout<<"Red\n";
        }else cout<<"Draw\n";

    }

    return 0;
}