首页 > 试题广场 >

太阳之华

[编程题]太阳之华
  • 热度指数:1963 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 768M,其他语言1536M
  • 算法知识视频讲解
太阳之华下
众生在游戏
白垩色的王子摆放了一个 n \times m 的棋盘,游戏开始时棋盘上的每一个格子要么是红色 `#` 的,要么是蓝色 `.` 的。
游戏规则是这样的:红方先手,双方交替进行游戏。每一方在自己的回合都可以选择一个由自己的颜色的格子组成的四连通区域,然后对于这个四连通区域的每一个格子:如果这个格子的上下左右有和该格子颜色不同的格子的话,就将这些格子染成该格子的颜色。当场上均为蓝色格子时,蓝方胜利;当场上均为红方格子时,红方胜利。
注:四连通区域指的是从区域内每一格出发,可通过四个方向,即上、下、左、右这四个方向的移动的组合,在不越出区域的前提下,到达区域内的任意格子。
例如:

这是一张 4 \times 4 的棋盘,左图中,红方选择较上方的那个四连通区域进行染色,染色之后,棋盘会变成右图这个样子。
现在给出初始棋盘,询问如果双方都足够聪明,有没有一方一定能够获得游戏胜利,或者是游戏永远结束不了而将以平局告终。

输入描述:
第一行输入一个整数 T(1 \le T \le 100),表示数据组数。
对于每一组数据,第一行输入两个整数 n,m(1 \le n \le \sum n \le 2000,1 \le m \le \sum m \le 2000),表示这个棋盘有 nm 列。
接下来 n 行,每行包含 m 个字符 c_{i,j},保证 c_{i,j} 一定为 `#` 或 `.`。`#` 表示第 i 行第 j 列在游戏开始时的颜色为红色,`.` 表示第 i 行第 j 列在游戏开始时的颜色为蓝色。


输出描述:
对于每一组数据,输出一行一个字符串 SS 一定为 "Red"、"Blue"、"Draw" 中的一种(不含引号),分别表示红方能获胜、蓝方能获胜、游戏永远无法结束。
示例1

输入

3
3 5
#.###
#.#.#
#.###
1 6
###...
2 3
...
...

输出

Red
Draw
Blue

说明

对于第一组数据,红方第一步选择较右边那个四联通块即可获胜。
头像 pandaC222
发表于 2026-03-24 00:43:54
本题是博弈题,思路很简单,只要观察一下我们就能注意到蓝色只有一种赢得情况,就是图中没有红色块,而对于红色这种情况也成立,由于红色是先手,所以只要红色第一次选择可以把蓝色全部变为红色就可以获胜,如果不可以就会陷入势均力敌的状态,大概手模一下就能知道。分析完毕,我们来用代码实现这个过程,我们首先存图记录 展开全文
头像 憨憨的竹林
发表于 2026-03-24 01:24:03
不难发现,由于红色先手,那么蓝色只有一种情况可以赢,就是开始的时候全是蓝色的那么红色怎么能赢呢,不难发现如果可以通过一次吞并直接把所有蓝色变成红色,那么红色能赢,否则没有斩草除根的后果就是达成平局假设初始有cnt个蓝色块那我们要做的也就是遍历每个红色连通块,看看他能不能吞掉所有蓝色块(即查看与他接壤 展开全文
头像 AliLexiWalker
发表于 2026-03-24 08:41:28
先把所有红色连通块找出来,然后统计每个红块“挨着”的蓝格数量:如果存在一个红块能挨到全部蓝格,红方先手第一步直接全染红,答案就是 Red。 如果一开始全蓝就是 Blue;否则红方做不到一步清场时,蓝方也永远不可能把红格变蓝,结果是 Draw。 void solve(){ int n,m;ci 展开全文
头像 IA3000
发表于 2026-03-24 09:19:34
#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&g 展开全文
头像 为芙宁娜献出心脏
发表于 2026-03-24 09:32:00
纯BFS,首先最开始模拟的时候我们很容易就会发现,对于红色,必须存在一个连通块和所有蓝色格子四联通,否则平局。 对于蓝色,则是除非全部都是蓝色格子,不然赢不了 所以直接BFS所有红色的连通块查找是否存在一个连通块和所有蓝色格子四联通就行了 代码如下: // BggBB 展开全文
头像 leo_ccc
发表于 2026-03-24 13:48:06
#include<bits/stdc++.h> #define ll long long #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define endl "\n" #d 展开全文
头像 olone
发表于 2026-03-24 15:31:36
import java.util.*; public class Main{ static int N = 2005; public static class pos{ int x; int y; pos(){} po 展开全文
头像 chenlan114
发表于 2026-03-24 16:17:44
#include<bits/stdc++.h> using namespace std; using ll=long long; const ll N=2e3+5; vector<vector<char>>g; vector<vector<bool&g 展开全文