2023年信息学奥赛NOI省选真题

NOI2023省选 DAY2 时间： 2023年4月 2日 08:30 ∼13:00 题目名称 过河卒 填数游戏 染色数组 题目类型 传统型 传统型 传统型 目录 zu game color 可执行文件名 zu game color 输入文件名 zu.in game.in color.in 输出文件名 zu.out game.out color.out 每个测试点时限 1.0秒 2.0秒 3.0秒 内存限制 1 GiB 1 GiB 1 GiB 测试点数目 20 25 20 测试点是否等分 是 是 是 提交源程序文件名 对于 C++ 语言 zu.cpp game.cpp color.cpp 编译选项 对于 C++ 语言 ‐O2 ‐std=c++14 ‐static .注 .意 .事 .项（ .请 .仔 .细 .阅 .读） 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. C/C++ 中函数main()的返回值类型必须是 int，程序正常结束时的返回值必须 是 0。 3. 提交的程序代码文件的放置位置请参考各省的具体要求。 4. 因违反以上三点而出现的错误或问题，申诉时一律不予受理。 5. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 6. 选手提交的程序源文件必须不大于 100KB。 7. 程序可使用的栈空间内存限制与题目的内存限制一致。 8. 全国统一评测时采用的机器配置为： Intel(R) Core(TM) i7-8700K CPU @3.70GHz ， 内存 32GB 。上述时限以此配置为准。 9. 只提供 Linux格式附加样例文件。 10. 评测在当前最新公布的 NOI Linux下进行，各语言的编译器版本以此为准。 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) 这三个格子中的一个，只要这 个目的地在棋盘内且没有障碍。 在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断 胜负（列在前面的优先）： • 黑棋子位于第一行。此时黑方胜。 • 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。 • 当前玩家不能进行任何合法操作。此时对方胜。 现在假设双方采用最优策略，不会进行不利于自己的移动。也就是说： • 若存在必胜策略，则会选择所有必胜策略中，不论对方如何操作，本方后续获胜 所需步数最大值最少的操作。 • 若不存在必胜策略，但存在不论对方如何行动，自己都不会落败的策略，则会选 择任意一种不败策略。 • 若不存在不败策略，则会选择在所有策略中，不论对方如何操作，对方后续获胜 所需步数最小值最大的操作。 如果在 100100 100 个回合之后仍不能分出胜负，则认为游戏平局。请求出游戏结束时 双方一共移动了多少步，或者判断游戏平局。 【输入格式】从文件 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 【样例