A6639 · 「联合省选 2023」过河卒

题目描述

有一个 $n$ 行 $m$ 列的棋盘。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置。棋盘上有一些 障碍，还有一个黑棋子和两个红棋子。 游戏的规则是这样的: 红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 $(i,j)$，那么它可以走到 $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ 中的一个，只要这个目的地在棋盘内且没有障碍且没有红方的另一个棋子。 黑方每次可以将自己的棋子向三个方向之一移动一格。具体地，假设这个黑棋子位置在 $(i,j)$，那么它可以走到 $(i-1,j),(i,j-1),(i,j+1)$ 这三个格子中的一个，只要这个目的地在棋盘内且没有障碍。 在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断胜负（列在前面的优先）： - 黑棋子位于第一行。此时黑方胜。 - 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。 - 当前玩家不能进行任何合法操作。此时对方胜。 现在假设双方采用最优策略，不会进行不利于自己的移动。也就是说: - 若存在必胜策略，则会选择所有必胜策略中，不论对方如何操作，本方后续获胜所需步数最大值最少的操作。 - 若不存在必胜策略，但存在不论对方如何行动，自己都不会落败的策略，则会选择任意一种不败策略。 - 若不存在不败策略，则会选择在所有策略中，不论对方如何操作，对方后续获胜所需步数最小值最大的操作。 如果在 $100^{100^{100}}$ 个回合之后仍不能分出胜负，则认为游戏平局。请求出游戏结束时双方一共移动了多少步，或者判断游戏平局。

输入格式

**本题有多组测试数据**。 输入的第一行包含两个整数 $\text{id},T$，分别表示测试点编号和数据组数。特别地，样例的 $\text{id}$ 为 $0$。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行包含两个正整数 $n,m$，表示棋盘的行数和列数。 接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，其中第 $i$ 行的第 $j$ 个字符表示棋盘上 $(i,j)$ 这个位置的状态。 在这些字符中：$\texttt{'.'}$ 表示空位；$\texttt{'\#'}$ 表示障碍物；$\texttt{'X'}$ 表示黑棋；$\texttt{'O'}$ 表示红棋。 保证黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一行。

输出格式

对于每组数据，输出一行字符串。 如果游戏平局，请输出一行 $\texttt{"Tie"}$。 如果红方胜，请输出一行 $\texttt{"Red t"}$。其中 $\texttt{t}$ 为游戏结束时双方移动的步数之和。显然这应该是一个奇数。 如果黑方胜，请输出一行 $\texttt{"Black t"}$。其中 $\texttt{t}$ 为游戏结束时双方移动的步数之和。显然这应该是一个偶数。 注意，请输出双引号内的字符串，不包含双引号。

输入输出样例

输入 #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

0 10
10 10
...#......
..#....#.#
....X..#..
..#.....#.
#.........
...###....
.O.......O
..........
........#.
......##.#
10 10
#.#...#...
...####..#
.#.....###
#..#O#..#.
.##...#.##
##.X###...
.#......#.
...#....##
..O.#..##.
....#.#.##
10 10
......##.#
.....#....
.......#..
.#..##O.##
.......#..
..#.#.....
..#.X.....
...O.....#
#...#.....
.........#
10 10
..........
..........
..........
..........
...O......
..........
..X.......
..........
##########
.......O..
10 10
.#...#....
.....#....
....##.###
.X.......#
.##....#.O
..#...#...
.##....#..
........##
.#..#.#.O.
.....###.#
10 1
.
O
.
X
.
O
.
#
.
#
5 5
O....
.#.#.
.....
#..#.
O#.X.
10 1
.
#
.
O
O
.
X
.
#
.
6 10
..........
..........
.........O
........X.
##########
....O.....
10 10
..........
..........
..........
...X......
..........
..........
.......O..
..........
##########
....O.....

输出 #2

Black 4
Red 5
Red 7
Red 7
Black 8
Red 3
Tie
Red 3
Red 19
Black 6

A6639 | 「联合省选 2023」过河卒

题目描述

输入格式

输出格式

输入输出样例

A6639 | $「联合省选 2023」过河卒$