#SXLK2023D. 过河卒

过河卒

题目背景

棋盘上有一个过河卒,需要走到底线。卒行走的规则是可以向左移动一格,向右移动一格或者向前移动一格。同时在棋盘上有两个另一方的棋子,需要拦截这个卒走到底线。这两个棋子的走法和帅一致,可以走到前后左右四个方向上相邻的格子。因此本题可以称为“帅拦过河卒”。

题目描述

有一个 nnmm 列的棋盘。我们用 (i,j)(i,j) 表示第 ii 行第 jj 列的位置。棋盘上有一些 障碍,还有一个黑棋子和两个红棋子。

游戏的规则是这样的: 红方先走,黑方后走,双方轮流走棋。红方每次可以选择一个红棋子,向棋盘的相邻一格走一步。具体而言,假设红方选择的这个棋子位置在 (i,j)(i,j),那么它可以走到 (i1,j),(i+1,j),(i,j1),(i,j+1)(i-1,j),(i+1,j),(i,j-1),(i,j+1) 中的一个,只要这个目的地在棋盘内且没有障碍且没有红方的另一个棋子。

黑方每次可以将自己的棋子向三个方向之一移动一格。具体地,假设这个黑棋子位置在 (i,j)(i,j),那么它可以走到 (i1,j),(i,j1),(i,j+1)(i-1,j),(i,j-1),(i,j+1) 这三个格子中的一个,只要这个目的地在棋盘内且没有障碍。

在一方行动之前,如果发生以下情况之一,则立即结束游戏,按照如下的规则判断胜负(列在前面的优先):

  • 黑棋子位于第一行。此时黑方胜。

  • 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。

  • 当前玩家不能进行任何合法操作。此时对方胜。

现在假设双方采用最优策略,不会进行不利于自己的移动。也就是说:

  • 若存在必胜策略,则会选择所有必胜策略中,不论对方如何操作,本方后续获胜所需步数最大值最少的操作。
  • 若不存在必胜策略,但存在不论对方如何行动,自己都不会落败的策略,则会选择任意一种不败策略。
  • 若不存在不败策略,则会选择在所有策略中,不论对方如何操作,对方后续获胜所需步数最小值最大的操作。

如果在 100100100100^{100^{100}} 个回合之后仍不能分出胜负,则认为游戏平局。请求出游戏结束时双方一共移动了多少步,或者判断游戏平局。

输入格式

本题有多组测试数据

输入的第一行包含两个整数 id,T\text{id},T,分别表示测试点编号和数据组数。特别地,样例的 id\text{id}00

接下来包含 TT 组数据,每组数据的格式如下:

第一行包含两个正整数 n,mn,m,表示棋盘的行数和列数。

接下来 nn 行,每行包含一个长度为 mm 的字符串,其中第 ii 行的第 jj 个字符表示棋盘上 (i,j)(i,j) 这个位置的状态。

在这些字符中:’.’\texttt{'.'} 表示空位;’#’\texttt{'\#'} 表示障碍物;’X’\texttt{'X'} 表示黑棋;’O’\texttt{'O'} 表示红棋。

保证黑棋恰好有一个,红棋恰好有两个,且黑棋不在第一行。

输出格式

对于每组数据,输出一行字符串。

如果游戏平局,请输出一行 "Tie"\texttt{"Tie"}

如果红方胜,请输出一行 "Red t"\texttt{"Red t"}。其中 t\texttt{t} 为游戏结束时双方移动的步数之和。显然这应该是一个奇数。

如果黑方胜,请输出一行 "Black t"\texttt{"Black t"}。其中 t\texttt{t} 为游戏结束时双方移动的步数之和。显然这应该是一个偶数。

注意,请输出双引号内的字符串,不包含双引号。

样例 #1

样例输入 #1

0 5
4 5
...#O
.#..#
#O#..
.#..X
3 3
#.#
O.O
.X.
3 3
O..
.#X
.O.
5 5
.....
.....
..O..
#..#.
O#.X.
9 9
...######
.#.......
.#######.
.#.#.....
.#O#.####
.#.#.....
.#######.
.#X......
.O.......

样例输出 #1

Black 0
Black 2
Black 2
Tie
Red 75

样例 #2

样例输入 #2

见附件中的 zu/zu2.in

样例输出 #2

见附件中的 zu/zu2.ans

提示

【样例 1 解释】

第一组数据,红方第一步没有可行的移动,所以黑方胜。

第二组数据,无论第一步红方怎么移动,黑方都可以在下一步让黑棋子与红棋子在同一个位置。

第三组数据,无论第一步红方怎么移动,黑方都可以将自己的棋子往上移动一枚来达成胜利。

第四组数据,有一个红棋子不能动。另一个红棋子可以在第三行移动来防止黑棋子进入第一行。黑棋子也可以一直在第五行移动。如果红棋子到达第五行,黑棋子可以选择从另一边逃走。

第五组数据,在最后一行的那个红棋子可以从左边绕一圈抓住黑棋子。注意另一个红棋子可以移动。

【样例 2 解释】

这个样例中的每一组数据都满足测试点 551313 中某一个测试点的限制。

【子任务】

对于所有的数据,保证:$1 \leq T \leq 10 ; 2 \leq n \leq 10 ; 1 \leq m \leq 10 ; \text{id}$ 等于测试点编号。

对于每组数据保证:棋盘上的黑棋恰好有一个,红棋恰好有两个,且黑棋不在第一 行。

  • 测试点 141 \sim 4:保证要么平局,要么红方在开始时无法移动。

  • 测试点 565 \sim 6:保证 n4n \geq 4 。保证棋盘上第 n1n-1 行的每一个格子都是障碍物,且 棋盘上其他行没有障碍物。保证黑棋在前 n2n-2 行,有一个红棋在前 n2n-2 行,另一个红棋在第 nn 行。

  • 测试点 797 \sim 9:保证 m=1m=1

  • 测试点 101310 \sim 13:保证要么平局,要么存在策略可以在 99 步之内结束游戏。

  • 测试点 142014 \sim 20:无特殊限制。

zu.zip