矩阵染色(Matrix Coloring)

题目描述

现在有一个 $n * n$ 的矩阵，刚开始矩阵里的每一个格子是没有颜色的。现在小 Z 需要通过染色刷子把矩阵中的元素染成特定的颜色。

小 Z 有两种染色刷子可以使用：行刷子和列刷子。

• 行刷子可以把一行刷成黑色
• 列刷子可以把一列刷成白色。

矩阵的每一行或者每一列最多刷一次，对于一个格子来说，后面刷的颜色会覆盖前面的颜色。

问小 Z 最少刷几次，就可以变成目标矩阵。

输入格式

第一行一个整数 $n$，表示矩阵的行数和列数。

接下里 $n$ 行，每行 $n$ 个元素，W 表示这个格子是白色或 B 表示这个格子是黑色，这些颜色表述的是这个 $n * n$ 的矩阵的最终需要的特定颜色。

输出格式

输出一行，表示最少步骤的操作方案，输出格式如下：

• 操作如 R#（行刷子）或者 C#（列刷子），# 表示行号或者列行。

如果有多个答案，输出字典序最小的方案（因为 'C' 的字典序小于 'R'，所以列操作小于行操作；同时，因为字典序最小，所以在多个答案的情况下，需要变换的行列编号也要最小）。

如果无法刷成目标矩阵，输出 "No solution"。

样例输入 #1

2
BB
WB

样例输出 #1

R2 C1 R1

样例输入 #2

2
BW
WB

样例输出 #2

No solution

数据范围

【样例 1 解释】

1. 执行 R2 操作后，矩阵如下（其中 '.' 表示没有颜色）：

..
BB

2. 执行 C1 操作后，矩阵如下（其中 '.' 表示没有颜色）：

W.
WB

3. 执行 R1 操作后，矩阵如下（其中 '.' 表示没有颜色）：

BB
WB

通过枚举所有的可能性，可以发现该方案是字典序最小的一个合法的方案。

【数据范围】

对于 $30\%$ 的数据，$n$ 的范围 $[1,5]$;

对于 $70\%$ 的数据，$n$ 的范围 $[1,100]$;

对于 $100\%$ 的数据，$n$ 的范围 $[1,500]$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接