#P11464. [2021年山东省队集训d6]Pajel游戏

    ID: 10612 提交答案题 尝试: 3 已通过: 1 难度: 6 上传者: 标签>图论动态规划CF2000构造搜索模拟DFS启发式搜索

[2021年山东省队集训d6]Pajel游戏

题目描述

给定一个 n×nn\times n 的方格。每个格子可以染成红色 M、蓝色 B,或者留空 -。

每一行的左、右两端和每一列的上、下两端各有一个提示。按提示所在的一端向内数,紧邻该端的格子是第 11 个。提示有三种:

  • - 表示这一端没有限制。
  • 0 表示整行或整列都留空。
  • kC 表示从这一端数,第一个染色的格子是第 kk 个,颜色为 CC。它前面的 k−1k-1 个格子必须留空。

两个染了同样颜色的格子如果共用一条边,就属于同一个同色连通块。红色和蓝色的四连通块总数为染色代价 pp。请给出一个满足所有提示的染色方案,并尽量使 pp 不超过目标代价 qq。

输入格式

本题共有 1010 组公开输入。下载输入数据,解压后可得到 pajel1.in 至 pajel10.in。

每个输入文件的格式如下:

  • 第一行两个正整数 n,qn,q,分别表示网格边长和目标代价。
  • 第二行 nn 个提示,按从左到右的顺序给出每一列上方的提示。
  • 接下来 nn 行,每行两个提示,依次给出对应行左侧和右侧的提示。
  • 最后一行 nn 个提示,按从左到右的顺序给出每一列下方的提示。

其中 1≤n≤5001\le n\le 500,1≤q≤n21\le q\le n^2。

输出格式

对第 ii 组输入,生成文件 pajel<i>.out,其中 <i> 用测试点编号替换。例如,第 11 组的文件名为 pajel1.out,第 1010 组为 pajel10.out。

每个输出文件包含 nn 行,每行恰好 nn 个字符,只能使用 M、B 和 -。将完成的输出文件放在同一个 ZIP 压缩包的根目录,上传该 ZIP。允许只提交部分测试点。

样例

5 3
1M - - - -
- -
1B 3B
0 -
- -
5M 1M
4B - 2M - -
M----
BBB--
-----
-MMMM
----M

样例有两个红色连通块和一个蓝色连通块,故 p=3p=3。

评分方式

每个测试点满分为 1010 分,总分为 100100 分。缺少对应输出文件、输出格式错误或方案不满足任意一条提示,该测试点得 00 分。

对合法方案,若 p≤qp\le q,该测试点得 1010 分。若 p>qp>q,得分为

$$\max\left\{1,\left\lfloor 10-8\cdot\frac{p-q}{\sqrt{q}}\right\rfloor\right\}.$$