#P11464. [2021年山东省队集训d6]Pajel游戏
[2021年山东省队集训d6]Pajel游戏
题目描述
给定一个 的方格。每个格子可以染成红色 M、蓝色 B,或者留空 -。
每一行的左、右两端和每一列的上、下两端各有一个提示。按提示所在的一端向内数,紧邻该端的格子是第 个。提示有三种:
-表示这一端没有限制。0表示整行或整列都留空。kC表示从这一端数,第一个染色的格子是第 个,颜色为 。它前面的 个格子必须留空。
两个染了同样颜色的格子如果共用一条边,就属于同一个同色连通块。红色和蓝色的四连通块总数为染色代价 。请给出一个满足所有提示的染色方案,并尽量使 不超过目标代价 。
输入格式
本题共有 组公开输入。下载输入数据,解压后可得到 pajel1.in 至 pajel10.in。
每个输入文件的格式如下:
- 第一行两个正整数 ,分别表示网格边长和目标代价。
- 第二行 个提示,按从左到右的顺序给出每一列上方的提示。
- 接下来 行,每行两个提示,依次给出对应行左侧和右侧的提示。
- 最后一行 个提示,按从左到右的顺序给出每一列下方的提示。
其中 ,。
输出格式
对第 组输入,生成文件 pajel<i>.out,其中 <i> 用测试点编号替换。例如,第 组的文件名为 pajel1.out,第 组为 pajel10.out。
每个输出文件包含 行,每行恰好 个字符,只能使用 M、B 和 -。将完成的输出文件放在同一个 ZIP 压缩包的根目录,上传该 ZIP。允许只提交部分测试点。
样例
5 3
1M - - - -
- -
1B 3B
0 -
- -
5M 1M
4B - 2M - -
M----
BBB--
-----
-MMMM
----M
样例有两个红色连通块和一个蓝色连通块,故 。
评分方式
每个测试点满分为 分,总分为 分。缺少对应输出文件、输出格式错误或方案不满足任意一条提示,该测试点得 分。
对合法方案,若 ,该测试点得 分。若 ,得分为
$$\max\left\{1,\left\lfloor 10-8\cdot\frac{p-q}{\sqrt{q}}\right\rfloor\right\}.$$