原题资料

题目背景

这是一道提交答案题。

题目描述

现有一个 $n\times n$ 的长方形网格。每个格子可以染为红色（用 M 表示）或者蓝色（用 B 表示），也可以不染色（用 - 表示）。

网格的四周写有提示。例如，在网格每一列的上方，均写有提示，形如 -, 0, 或 $nC$,其中 $n$ 为数字而 $C$ 为 M 或 B 之一。其中，- 表示无限制，0 表示该列的格子均不染色，而 $nC$ 形式则代表该列从上往下数，第一个染色的格子为第 $n$ 个格子，它的颜色为 $C$。

每一列的下方同样写有提示，这时描述的则是从下往上数，第一个染色的格子。在网格每一行的左侧和右侧类似地写有提示，分别描述该行从左往右和从右往左数的第一个染 色的格子。

染色的代价为同色四连通块数。请你给出一种方案，使得代价不超过 $q$。

输入格式

这是一道提交答案题，共有 $10$ 组输入数据，这些数据命名为 pajel1.in $\sim$ pajel10.in。

第一行两个正整数 $n, q$, 表示网格的边长和目标代价。

接下来一行 $n$ 个字符串，表示各列上方的提示。

接下来 $n$ 行，每行两个字符串，表示该行左侧和右侧的提示。

接下来一行 $n$ 个字符串，表示各列下方的提示。

输出格式

对于每组输入数据，你需要提交相应的输出文件 pajel1.out $\sim$ pajel10.out。

$n$ 行，每行 $n$ 个字符，表示你的染色方案。

输入输出样例 #1

输入 #1

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

输出 #1

M----
BBB--
-----
-MMMM
----M

说明/提示

评分方式

本题共 $10$ 个测试点，评分方式为：

若方案不满足提示要求，得分为 $0$。

若方案满足提示要求，设你的方案代价为 $p$, 评分参数为 $q$, 若 $p ≤ q$, 该测试点得 $10$ 分；否则该测试点得分为 $\max \{1,\lfloor 10- 8\times \frac{p-q}{\sqrt q}\rfloor\}$。

编译下发文件中的 checker.cpp, 把可执行文件与输入、输出文件放在同一目录内运行，可以评测本题。

参数：如果指定了参数 id, 则只评测第 $id$ 个测试点。