本题是博弈题,思路很简单,只要观察一下我们就能注意到蓝色只有一种赢得情况,就是图中没有红色块,而对于红色这种情况也成立,由于红色是先手,所以只要红色第一次选择可以把蓝色全部变为红色就可以获胜,如果不可以就会陷入势均力敌的状态,大概手模一下就能知道。
分析完毕,我们来用代码实现这个过程,我们首先存图记录蓝色块红色块数量,先特判没有红色块或者蓝色块的情况,然后紧接着判断红色是否可以一步赢,实际上就是记录图中是否存在一个红色连通块使得其能接触到的(四联通)蓝色块是否等于我们统计的所有蓝色块数,这里可以用bfs来模拟这个过程,记得用vis数组记录哪个点走过了。
代码如下:(今天有早八(哭))
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
void solve(){
int n,m;cin>>n>>m;
vector<vector<char>> pos(n+1,vector<char>(m+1));
int cntr=0,cntb=0;
for(int i=1;i<=n;i++){
string s;cin>>s;
for(int j=1;j<=m;j++){
pos[i][j]=s[j-1];
if(s[j-1]=='.') cntb++;
else cntr++;
}
}
if(cntr==0){
cout<<"Blue\n";
return;
}
if(cntb==0){
cout<<"Red\n";
return;
}
vector<vector<bool>> vis(n+1,vector<bool>(m+1));
queue<pair<int,int>> q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(pos[i][j]=='.') continue;
if(vis[i][j]) continue;
if(pos[i][j]=='#') q.push({i,j});
int cnt=0;
vector<vector<bool>> blue(n+1,vector<bool>(m+1));
while(q.size()){
auto [x,y]=q.front();q.pop();
for(int k=0;k<4;k++){
int nx=x+dx[k],ny=y+dy[k];
if(nx<1||ny<1||nx>n||ny>m) continue;
if(vis[nx][ny]) continue;
if(blue[nx][ny]) continue;
if(pos[nx][ny]=='#') vis[nx][ny]=1,q.push({nx,ny});
else{
cnt++;
blue[nx][ny]=1;
}
}
}
if(cnt==cntb){
cout<<"Red\n";
return;
}
}
}
cout<<"Draw\n";
}
signed main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
cin>>t;
while(t--){
solve();
}return 0;
}

京公网安备 11010502036488号