#2260. 过河卒

    ID: 2260 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest1199来源:qoj.ac数据:公开样例字符串博弈论

过河卒

过河卒

题目描述

NOI2023 省选 DAY2 过河卒(zu) 过河卒(zu) 【题目背景】 棋盘上有一个过河卒,需要走到底线。卒行走的规则是可以向左移动一格,向右移 动一格或者向前移动一格。同时在棋盘上有两个另一方的棋子,需要拦截这个卒走到底 线。这两个棋子的走法和帅一致,可以走到前后左右四个方向上相邻的格子。因此本题 可以称为“帅拦过河卒”。 【题目描述】 有一个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) 这三个格子中的一个,只要这 个目的地在棋盘内且没有障碍。 在一方行动之前,如果发生以下情况之一,则立即结束游戏,按照如下的规则判断 胜负(列在前面的优先): • 黑棋子位于第一行。此时黑方胜。 • 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。 • 当前玩家不能进行任何合法操作。此时对方胜。 现在假设双方采用最优策略,不会进行不利于自己的移动。也就是说: • 若存在必胜策略,则会选择所有必胜策略中,不论对方如何操作,本方后续获胜 所需步数最大值最少的操作。 • 若不存在必胜策略,但存在不论对方如何行动,自己都不会落败的策略,则会选 择任意一种不败策略。 • 若不存在不败策略,则会选择在所有策略中,不论对方如何操作,对方后续获胜 所需步数最小值最大的操作。 如果在100100100 个回合之后仍不能分出胜负,则认为游戏平局。请求出游戏结束时 双方一共移动了多少步,或者判断游戏平局。 【输入格式】 从文件zu.in 中读入数据。 .本.题.有.多.组.测.试.数.据。 第2 页 共12 页

NOI2023 省选 DAY2 过河卒(zu) 输入的第一行包含两个整数id, T,分别表示测试点编号和数据组数。特别地,样例 的id 为0。 接下来包含T 组数据,每组数据的格式如下: 第一行包含两个正整数n, m,表示棋盘的行数和列数。 接下来n 行,每行包含一个长度为m 的字符串,其中第i 行的第j 个字符表示棋 盘上(i, j) 这个位置的状态。 在这些字符中:'.' 表示空位;'#' 表示障碍物;'X' 表示黑棋;'O' 表示红棋。 保证黑棋恰好有一个,红棋恰好有两个,且黑棋不在第一行。 【输出格式】 输出到文件zu.out 中。 对于每组数据,输出一行字符串。 如果游戏平局,请输出一行"Tie"。 如果红方胜,请输出一行"Red t"。其中t 为游戏结束时双方移动的步数之和。显 然这应该是一个奇数。 如果黑方胜,请输出一行"Black t"。其中t 为游戏结束时双方移动的步数之和。 显然这应该是一个偶数。 注意,请输出双引号内的字符串,不包含双引号。 【样例1 输入】 1 0 5 2 4 5 3 ...#O 4 .#..# 5 #O#.. 6 .#..X 7 3 3 8 #.# 9 O.O 10 .X. 11 3 3 12 O.. 13 .#X 14 .O. 15 5 5 16 ..... 第3 页 共12 页

NOI2023 省选 DAY2 过河卒(zu) 17 ..... 18 ..O.. 19 #..#. 20 O#.X. 21 9 9 22 ...###### 23 .#....... 24 .#######. 25 .#.#..... 26 .#O#.#### 27 .#.#..... 28 .#######. 29 .#X...... 30 .O....... 【样例1 输出】 1 Black 0 2 Black 2 3 Black 2 4 Tie 5 Red 75 【样例1 解释】 第一组数据,红方第一步没有可行的移动,所以黑方胜。 第二组数据,无论第一步红方怎么移动,黑方都可以在下一步让黑棋子与红棋子在 同一个位置。 第三组数据,无论第一步红方怎么移动,黑方都可以将自己的棋子往上移动一格来 达成胜利。 第四组数据,有一个红棋子不能动。另一个红棋子可以在第三行移动来防止黑棋子 进入第一行。黑棋子也可以一直在第五行移动。如果红棋子到达第五行,黑棋子可以选 择从另一边逃走。 第五组数据,在最后一行的那个红棋子可以从左边绕一圈抓住黑棋子。注意另一个 红棋子可以移动。 第4 页 共12 页

NOI2023 省选 DAY2 过河卒(zu) 【样例2】 见选手目录下的zu/zu2.in 与zu/zu2.ans。 【样例2 解释】 这个样例中的每一组数据都满足测试点5 到13 中某一个测试点的限制。 【子任务】 对于所有的数据,保证:1 ≤T ≤10;2 ≤n ≤10;1 ≤m ≤10;id 等于测试点编号。 对于每组数据保证:棋盘上的黑棋恰好有一个,红棋恰好有两个,且黑棋不在第一 行。 • 测试点1 ∼4:保证要么平局,要么红方在开始时无法移动。 • 测试点5 ∼6:保证n ≥4。保证棋盘上第n −1 行的每一个格子都是障碍物,且 棋盘上其他行没有障碍物。保证黑棋在前n −2 行,有一个红棋在前n −2 行,另 一个红棋在第n 行。 • 测试点7 ∼9:保证m = 1。 • 测试点10 ∼13:保证要么平局,要么存在策略可以在9 步之内结束游戏。 • 测试点14 ∼20:无特殊限制。 第5 页 共12 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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.......
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.....
Black 4
Red 5
Red 7
Red 7
Black 8
Red 3
Tie
Red 3
Red 19
Black 6