太阳之华下白垩色的王子摆放了一个
众生在游戏
第一行输入一个整数，表示数据组数。
对于每一组数据，第一行输入两个整数，表示这个棋盘有
行
列。
接下来，保证
行第
列在游戏开始时的颜色为红色，`.` 表示第
对于每一组数据，输出一行一个字符串，
3 3 5 #.### #.#.# #.### 1 6 ###... 2 3 ... ...
Red Draw Blue
对于第一组数据，红方第一步选择较右边那个四联通块即可获胜。
本题是博弈题，思路很简单，只要观察一下我们就能注意到蓝色只有一种赢得情况，就是图中没有红色块，而对于红色这种情况也成立，由于红色是先手，所以只要红色第一次选择可以把蓝色全部变为红色就可以获胜，如果不可以就会陷入势均力敌的状态，大概手模一下就能知道。
分析完毕，我们来用代码实现这个过程，我们首先存图记录蓝色块红色块数量，先特判没有红色块或者蓝色块的情况，然后紧接着判断红色是否可以一步赢，实际上就是记录图中是否存在一个红色连通块使得其能接触到的（四联通）蓝色块是否等于我们统计的所有蓝色块数，这里可以用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;
}
不难发现，由于红色先手，那么蓝色只有一种情况可以赢，就是开始的时候全是蓝色的
那么红色怎么能赢呢，不难发现如果可以通过一次吞并直接把所有蓝色变成红色，那么红色能赢，否则没有斩草除根的后果就是达成平局
假设初始有cnt个蓝色块
那我们要做的也就是遍历每个红色连通块，看看他能不能吞掉所有蓝色块（即查看与他接壤的蓝色块数量是否等于cnt）
用vis来判断该连通块是否走过，用visb来确保一个蓝色块不会被多次计算数量
大概就是这样，可以详见代码和注释
（主包感觉逻辑有点搞的还是，但是居然一遍就过了完全没有调，感觉还是很开心的，虽然感觉可能有的优化没有做好导致代码还是有点慢）
#include <bits/stdc++.h>
using namespace std;
// #define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int hash_base = 881;
const int N = 1e6 + 10;
const double EPS = 1e-8;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, z, len, t, l, r, cur;
string s1, s2;
cin >> n >> m;
vector c(n + 1,vector<char>(m + 1)); // 存字符
vector vis(n + 1, vector<bool>(m + 1)),visb(n + 1,vector<bool>(m + 1)); // vis数组判断红色块所在的连通块是否被遍历过，visb数组保证一个蓝色块不会被多次计入
for (ll i = 1; i <= n;i++)
{
for (ll j = 1; j <= m;j++)
{
cin >> c[i][j];
if (c[i][j] == '.') // 读入数据，以及统计蓝色块数量
cnt++;
}
}
if (cnt == n * m) // 蓝色占据全部，蓝赢
{
cout << "Blue" << endl;
return;
}
if (cnt == 0) // 红色占据全部，红赢
{
cout << "Red" << endl;
return;
}
auto dfs = [&](auto dfs, ll x, ll y) -> void // dfs遍历
{
for (ll i = 0; i < 4;i++)
{
ll nx = x + dir[i][0];
ll ny = y + dir[i][1];
if (nx > n || nx < 1 || ny > m || ny < 1) // 如果四周的块会超过边界，那么违法，不管
continue;
if (c[nx][ny] == '#') // 如果四周是红色块，那么处于一个连通块内，如果它没有被走过，就继续dfs遍历四周的点，并且记录它已经在连通块内被遍历过了
{
if (vis[nx][ny])
continue;
vis[nx][ny] = 1;
dfs(dfs, nx, ny);
}
if (c[nx][ny] == '.') // 如果四周是蓝色块，那么累计次数（用visb数组确保不会被重复计算）
{
if (visb[nx][ny])
continue;
visb[nx][ny] = 1;
num++;
}
}
};
for (ll i = 1; i <= n; i++)
{
for (ll j = 1; j <= m; j++)
{
if (c[i][j] == '#' && vis[i][j] == 0) // 当碰到红色块且它没有在连通块里被遍历过，说明它属于一个新的连通块，我们要对它进行dfs遍历
{
num = 0;
for (ll k = 1; k <= n; k++)
{
for (ll l = 1; l <= m; l++) // 重置visb数组的值都为0
visb[k][l] = 0;
}
dfs(dfs, i, j); // 进行dfs
if (num == cnt) // 如果与该红色连通块接壤的蓝色块数量等于总蓝色块的数量，那么说明可以通过一次扩张把所有蓝色变为红色，红赢
{
cout << "Red" << endl;
return;
}
}
}
}
cout << "Draw" << endl; // 否则势均力敌达成无限循环，平局
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/ 类似的bfs写法：（注释懒得再抄一遍了）（这题bfs和dfs没有实质区别，而且bfs会更快） #include <bits/stdc++.h>
using namespace std;
// #define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int hash_base = 881;
const int N = 1e6 + 10;
const double EPS = 1e-8;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, z, len, t, l, r, cur;
string s1, s2;
cin >> n >> m;
vector c(n + 1,vector<char>(m + 1));
vector vis(n + 1, vector<bool>(m + 1));
queue<pll> q;
for (ll i = 1; i <= n;i++)
{
for (ll j = 1; j <= m;j++)
{
cin >> c[i][j];
if (c[i][j] == '.')
cnt++;
}
}
if (cnt == n * m)
{
cout << "Blue" << endl;
return;
}
if (cnt == 0)
{
cout << "Red" << endl;
return;
}
for (ll k = 1; k <= n; k++)
{
for (ll j = 1; j <= m; j++)
{
if (c[k][j] == '#' && vis[k][j] == 0)
{
num = 0;
vector visb(n + 1, vector<bool>(m + 1));
q.push({k, j});
while (q.size())
{
auto [x,y] = q.front();
q.pop();
for (ll i = 0; i < 4; i++)
{
ll nx = x + dir[i][0];
ll ny = y + dir[i][1];
if (nx > n || nx < 1 || ny > m || ny < 1)
continue;
if (c[nx][ny] == '#')
{
if (vis[nx][ny])
continue;
vis[nx][ny] = 1;
q.push({nx, ny});
}
if (c[nx][ny] == '.')
{
if (visb[nx][ny])
continue;
visb[nx][ny] = 1;
num++;
}
}
}
if (num == cnt)
{
cout << "Red" << endl;
return;
}
}
}
}
cout << "Draw" << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
