P13390 [GCJ 2010 #1A] Rotate

在激动人心的 Join-$K$ 游戏中，红色和蓝色棋子被投入一个 $N \times N$ 的棋盘。棋盘是竖直放置的，因此棋子会下落到该列最底部的空位。例如，考虑以下两种棋盘状态： ``` - 合法状态 - ....... ....... ....... ....R.. ...RB.. ..BRB.. .RBBR.. - 非法状态 - ....... ....... ....... ....... 错误 -> ..BR... ...R... .RBBR.. ``` 在这些图中，每个 '.' 表示一个空位，每个 'R' 表示一个红色棋子，每个 'B' 表示一个蓝色棋子。左边的状态是合法的，而右边的状态不是。原因是第三列中有一个棋子（箭头所指）没有落到其下方的空位上。 如果某个玩家能够将至少 $K$ 个同色棋子连成一行（可以是横向、纵向或对角线），则该玩家获胜。四种可能的连线方向如下所示： ``` - 四连子 - R RRRR R R R R R R R R R R R ``` 在题目开头的“合法状态”示意图中，两个玩家都已经连成了两个棋子，但都没有连成三个。 现在，你正处于一场激烈的 Join-$K$ 游戏中，并且你有一个巧妙的计划确保获胜！当你的对手不注意时，你准备将棋盘顺时针旋转 $90$ 度。然后，重力会让棋子在新方向上再次下落，形成如下状态： ``` - 初始 - ....... ....... ....... ...R... ...RB.. ..BRB.. .RBBR.. - 旋转 - ....... R...... BB..... BRRR... RBB.... ....... ....... - 重力作用 - ....... ....... ....... R...... BB..... BRR.... RBBR... ``` 不幸的是，你只有一次旋转的机会，在对手发现之前。 现在只剩下选择合适的时机出手了。给定一个棋盘状态，请你判断在顺时针旋转棋盘并让重力生效后，哪一方（或双方！）会在棋盘上连成 $K$ 个棋子。 ### 注意 - 你只能旋转棋盘一次。 - 假设重力只在棋盘完全旋转后才会生效。 - 只有在重力作用结束后才检查是否有玩家获胜。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据，每组测试数据的第一行为两个整数 $N$ 和 $K$。接下来的 $N$ 行，每行恰好 $N$ 个字符，表示棋盘的初始状态，格式与上文示意图一致。 每组测试数据中的初始状态都是 Join-$K$ 游戏中可能出现的合法状态。特别地，初始状态下不会有玩家已经连成 $K$ 个棋子。

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 "Red"、"Blue"、"Neither" 或 "Both" 之一，表示在旋转棋盘并让重力生效后，哪一方（或双方）会连成 $K$ 个棋子。

**数据范围** - $1 \leqslant T \leqslant 100$。 - $3 \leqslant K \leqslant N$。 **小数据范围（11 分，测试点 1 - 可见）** - $3 \leqslant N \leqslant 7$。 **大数据范围（12 分，测试点 2 - 隐藏）** - $3 \leqslant N \leqslant 50$。 由 ChatGPT 4.1 翻译