题目背景

译自 Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection) D2T1。$\texttt{15s,0.5G}$。

题目描述

给定 $N\times M$ 的黑白矩阵。用尽可能少数量的矩形覆盖住所有黑色格子，要求：

• 每个黑色格子恰好被一个矩形覆盖；
• 任意两个矩形不重叠；
• 矩形不覆盖白色格子。

并输出方案。

输入格式

第一行，两个正整数 $N,M$。

接下来一个 $N\times M$ 的矩阵，每个位置是 $\texttt{C}$ 或者 $\texttt{B}$。其中，$\texttt{C}$ 代表黑色（克罗地亚语「crno」），$\texttt{B}$ 代表白色（克罗地亚语「bijelo」）。

输出格式

输出 $N$ 行，每行 $M$ 个数，表示你的方案：

• 未被覆盖的区域，用 $0$ 表示；
• 否则，设使用了 $K$ 个矩形，将矩形用 $1\sim K$ 标号后，对应位置用覆盖它的矩形编号表示。

每一行相邻的数要用空格隔开。

4 5
CCBCB
CCBBB
CCCBB
CCCBB

1 1 0 2 0
1 1 0 0 0
3 3 3 0 0
3 3 3 0 0

7 5
CCCBB
BCBBB
BCCCB
BCCCB
CCCCC
BBBBB
BCCCB

1 1 1 0 0
0 2 0 0 0
0 3 3 3 0
0 3 3 3 0
4 4 4 4 4
0 0 0 0 0
0 5 5 5 0

5 11
BBCCCBCCCBC
BCCBCBBCCCC
CCCCBCCCCCC
BCBCCCBCCCB
CCCCBCBBCCB

0 0 1 1 1 0 2 2 2 0 3
0 4 4 0 5 0 0 6 6 6 3
7 7 7 7 0 8 8 6 6 6 3
0 9 0 10 10 10 0 6 6 6 0
11 11 11 11 0 12 0 0 13 13 0

提示

对于 $100\%$ 的数据，保证 $1\le N,M\le 500$。

【计分方式】

如果你输出的是最优解，得满分。

否则，设最优解用的矩形数量为 $A$，你的解用的矩形数量为 $B$，该测试点得分为 $0.75\cdot (A/B)^{10}\cdot 5$ 分。