不难发现，由于红色先手，那么蓝色只有一种情况可以赢，就是开始的时候全是蓝色的
那么红色怎么能赢呢，不难发现如果可以通过一次吞并直接把所有蓝色变成红色，那么红色能赢，否则没有斩草除根的后果就是达成平局
假设初始有cnt个蓝色块
那我们要做的也就是遍历每个红色连通块，看看他能不能吞掉所有蓝色块（即查看与他接壤的蓝色块数量是否等于cnt）
用vis来判断该连通块是否走过，用visb来确保一个蓝色块不会被多次计算数量
大概就是这样，可以详见代码和注释
（主包感觉逻辑有点搞的还是，但是居然一遍就过了完全没有调，感觉还是很开心的，虽然感觉可能有的优化没有做好导致代码还是有点慢）
dfs写法：
#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;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
京公网安备 11010502036488号