{"problem":{"name":"[省选联考 2023] 过河卒","description":{"content":"有一个 $n$ 行 $m$ 列的棋盘。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置。棋盘上有一些障碍，还有一个黑棋子和两个红棋子。 游戏的规则是这样的：红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 $(i,j)$，那么它可以走到 $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ 中","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9169"},"statements":[{"statement_type":"Markdown","content":"有一个 $n$ 行 $m$ 列的棋盘。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置。棋盘上有一些障碍，还有一个黑棋子和两个红棋子。\n\n游戏的规则是这样的：红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 $(i,j)$，那么它可以走到 $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ 中的一个，只要这个目的地在棋盘内且没有障碍且没有红方的另一个棋子。\n\n黑方每次可以将自己的棋子向三个方向之一移动一格。具体地，假设这个黑棋子位置在 $(i,j)$，那么它可以走到 $(i-1,j),(i,j-1),(i,j+1)$ 这三个格子中的一个，只要这个目的地在棋盘内且没有障碍。\n\n在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断胜负（列在前面的优先）：\n\n- 黑棋子位于第一行。此时黑方胜。\n\n- 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。\n\n- 当前玩家不能进行任何合法操作。此时对方胜。\n\n现在假设双方采用最优策略，不会进行不利于自己的移动。也就是说:\n\n- 若存在必胜策略，则会选择所有必胜策略中，不论对方如何操作，本方后续获胜所需步数最大值最少的操作。\n- 若不存在必胜策略，但存在不论对方如何行动，自己都不会落败的策略，则会选择任意一种不败策略。\n- 若不存在不败策略，则会选择在所有策略中，不论对方如何操作，对方后续获胜所需步数最小值最大的操作。\n\n如果在 $100^{100^{100}}$ 个回合之后仍不能分出胜负，则认为游戏平局。请求出游戏结束时双方一共移动了多少步，或者判断游戏平局。\n\n## Input\n\n**本题有多组测试数据**。\n\n输入的第一行包含两个整数 $\\text{id},T$，分别表示测试点编号和数据组数。特别地，样例的 $\\text{id}$ 为 $0$。\n\n接下来包含 $T$ 组数据，每组数据的格式如下：\n\n第一行包含两个正整数 $n,m$，表示棋盘的行数和列数。\n\n接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，其中第 $i$ 行的第 $j$ 个字符表示棋盘上 $(i,j)$ 这个位置的状态。\n\n在这些字符中：$\\texttt{'.'}$ 表示空位；$\\texttt{'\\#'}$ 表示障碍物；$\\texttt{'X'}$ 表示黑棋；$\\texttt{'O'}$ 表示红棋。\n\n保证黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一行。\n\n## Output\n\n对于每组数据，输出一行字符串。\n\n如果游戏平局，请输出一行 $\\texttt{\"Tie\"}$。\n\n如果红方胜，请输出一行 $\\texttt{\"Red t\"}$。其中 $\\texttt{t}$ 为游戏结束时双方移动的步数之和。显然这应该是一个奇数。\n\n如果黑方胜，请输出一行 $\\texttt{\"Black t\"}$。其中 $\\texttt{t}$ 为游戏结束时双方移动的步数之和。显然这应该是一个偶数。\n\n注意，请输出双引号内的字符串，不包含双引号。\n\n[samples]\n\n## Background\n\n棋盘上有一个过河卒，需要走到底线。卒行走的规则是可以向左移动一格，向右移动一格或者向前移动一格。同时在棋盘上有两个另一方的棋子，需要拦截这个卒走到底线。这两个棋子的走法和帅一致，可以走到前后左右四个方向上相邻的格子。因此本题可以称为“帅拦过河卒”。\n\n## Note\n\n**【样例 1 解释】**\n\n第一组数据，红方第一步没有可行的移动，所以黑方胜。\n\n第二组数据，无论第一步红方怎么移动，黑方都可以在下一步让黑棋子与红棋子在同一个位置。\n\n第三组数据，无论第一步红方怎么移动，黑方都可以将自己的棋子往上移动一枚来达成胜利。\n\n第四组数据，有一个红棋子不能动。另一个红棋子可以在第三行移动来防止黑棋子进入第一行。黑棋子也可以一直在第五行移动。如果红棋子到达第五行，黑棋子可以选择从另一边逃走。\n\n第五组数据，在最后一行的那个红棋子可以从左边绕一圈抓住黑棋子。注意另一个红棋子可以移动。\n\n**【样例 2 解释】**\n\n这个样例中的每一组数据都满足测试点 $5$ 到 $13$ 中某一个测试点的限制。\n\n**【子任务】**\n\n对于所有的数据，保证：$1 \\leq T \\leq 10$，$2 \\leq n \\leq 10$，$1 \\leq m \\leq 10$，$\\text{id}$ 等于测试点编号。\n\n对于每组数据保证：棋盘上的黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一 行。\n\n- 测试点 $1 \\sim 4$：保证要么平局，要么红方在开始时无法移动。\n\n- 测试点 $5 \\sim 6$：保证 $n \\geq 4$ 。保证棋盘上第 $n-1$ 行的每一个格子都是障碍物，且 棋盘上其他行没有障碍物。保证黑棋在前 $n-2$ 行，有一个红棋在前 $n-2$ 行，另一个红棋在第 $n$ 行。\n\n- 测试点 $7 \\sim 9$：保证 $m=1$。\n\n- 测试点 $10 \\sim 13$：保证要么平局，要么存在策略可以在 $9$ 步之内结束游戏。\n\n- 测试点 $14 \\sim 20$：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9169","tags":["博弈论","各省省选","2023","O2优化","广度优先搜索 BFS","拓扑排序"],"sample_group":[["0 5\n4 5\n...#O\n.#..#\n#O#..\n.#..X\n3 3\n#.#\nO.O\n.X.\n3 3\nO..\n.#X\n.O.\n5 5\n.....\n.....\n..O..\n#..#.\nO#.X.\n9 9\n...######\n.#.......\n.#######.\n.#.#.....\n.#O#.####\n.#.#.....\n.#######.\n.#X......\n.O.......\n","Black 0\nBlack 2\nBlack 2\nTie\nRed 75\n"],["见附件中的 zu/zu2.in","见附件中的 zu/zu2.ans"]],"created_at":"2026-03-03 11:09:25"}}