P11224 [COTS 2019] 挑战 Izazov

译自 [Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2019/) 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$ 标号后，对应位置用覆盖它的矩形编号表示。 每一行相邻的数要用空格隔开。

对于 $100\%$ 的数据，保证 $1\le N,M\le 500$。 | 测试点编号 | $N,M\le $ | 得分 | | :--: | :--: |:--: | | $ 1\sim 5 $ | $ 26 $ | $ 25 $ | | $ 6\sim 10 $ | $ 100 $ | $ 25 $ | | $ 11\sim 15 $ | $ 250 $ | $ 25 $ | | $ 16\sim 20 $ | $ 500 $ |$ 25 $ | 【计分方式】 如果你输出的是最优解，得满分。 否则，设最优解用的矩形数量为 $A$，你的解用的矩形数量为 $B$，该测试点得分为 $0.75\cdot (A/B)^{10}\cdot 5$ 分。