A6639. 「联合省选 2023」过河卒
编程题
省选/NOI-
知识点
题目描述
有一个 $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}}$ 个回合之后仍不能分出胜负，则认为游戏平局。请求出游戏结束时双方一共移动了多少步，或者判断游戏平局。
游戏的规则是这样的: 红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 $(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'}$ 表示红棋。
保证黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一行。
输入的第一行包含两个整数 $\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}$ 为游戏结束时双方移动的步数之和。显然这应该是一个偶数。
注意，请输出双引号内的字符串，不包含双引号。
如果游戏平局，请输出一行 $\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
说明/提示
对于所有的数据，保证：$1 \leq T \leq 10 ; 2 \leq n \leq 10 ; 1 \leq m \leq 10 ; \text{id}$ 等于测试点编号。
对于每组数据保证：棋盘上的黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一 行。
- 测试点 $1 \sim 4$：保证要么平局，要么红方在开始时无法移动。
- 测试点 $5 \sim 6$：保证 $n \geq 4$ 。保证棋盘上第 $n-1$ 行的每一个格子都是障碍物，且 棋盘上其他行没有障碍物。保证黑棋在前 $n-2$ 行，有一个红棋在前 $n-2$ 行，另一个红棋在第 $n$ 行。
- 测试点 $7 \sim 9$：保证 $m=1$。
- 测试点 $10 \sim 13$：保证要么平局，要么存在策略可以在 $9$ 步之内结束游戏。
- 测试点 $14 \sim 20$：无特殊限制。
对于每组数据保证：棋盘上的黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一 行。
- 测试点 $1 \sim 4$：保证要么平局，要么红方在开始时无法移动。
- 测试点 $5 \sim 6$：保证 $n \geq 4$ 。保证棋盘上第 $n-1$ 行的每一个格子都是障碍物，且 棋盘上其他行没有障碍物。保证黑棋在前 $n-2$ 行，有一个红棋在前 $n-2$ 行，另一个红棋在第 $n$ 行。
- 测试点 $7 \sim 9$：保证 $m=1$。
- 测试点 $10 \sim 13$：保证要么平局，要么存在策略可以在 $9$ 步之内结束游戏。
- 测试点 $14 \sim 20$：无特殊限制。