首页 > 试题广场 >

太阳之华

[编程题]太阳之华
  • 热度指数：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)，表示这个棋盘有 n 行 m 列。
接下来 n 行，每行包含 m 个字符 c_{i,j}，保证 c_{i,j} 一定为 `#` 或 `.`。`#` 表示第 i 行第 j 列在游戏开始时的颜色为红色，`.` 表示第 i 行第 j 列在游戏开始时的颜色为蓝色。


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

输入

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

输出

Red
Draw
Blue

说明

对于第一组数据，红方第一步选择较右边那个四联通块即可获胜。
算法知识视频讲解
添加回答
Java
牛客203596504号头像 牛客203596504号
博弈题首先找策略：
我们看到规则只允许吞并上下左右的方格，反过来说，如果一个方格上下左右同色，它就是安全的。
也就意味着，被我选中的方格，扩张后(上下左右同色)，对方是无法吞并它的，它能好端端的回来。
找到不败法则：只要我还有格子，哪怕只剩一个，我每轮都选它，每轮都安全，则不败。
双方都“不败”也就是平局。
由于红方先手，所以如果红方一步致胜，则红胜；不能一步致胜，则平局；开局全蓝，则蓝胜。

现在策略找到了，我们如何用代码实现策略呢？
第一步，找到红方所有的连通块。怎么找？
我们用一个二维数组存储连通块编号，然后在地图上遍历每个格子，找红色。
每找到一个没有连通块编号的红色格子，以它为起点DFS遍历，把整个连通块标上编号。
然后继续，将所有红色格子标上连通块编号。
10222
10202
10222
(我们找到了两个连通块)
第二步，找到一步取胜的办法。怎么找？
要尝试每个连通块么？不，那样太麻烦了。
我们反过来想。每个蓝色格子要被吞并，必然来自上下左右的红色格子。
如果想一步取胜，那个连通块的成员必然与每个蓝色格子全部相邻。
所以我们只需遍历所有蓝色格子的上下左右的连通块编号。
如果有连通块编号每次都出现，那就能一招制胜。如果没有，就赢不了。
(1,2) 上* 左1 右2 下0
(2,2) 上0 左1 右2 下0
(2,4) 上2 左2 右2 下2
(3,2) 上0 左1 右2 下*
(红方连通块2可以取胜)
发表于 2026-03-24 03:24:21 回复(0)
提交观点

问题信息

难度：
2条回答 18浏览

热门推荐

相关试题

太阳之华

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号