Мирко нашел на улице доску, состоящую из $R \times S$ полей (единичных квадратов), расположенных в $R$ строках и $S$ столбцах. В тот момент, когда Мирко нашел доску, все её поля были белого цвета. Мирко решил покрасить некоторые поля в черный цвет. После этого он отправил доску своему другу Славко вместе со следующим сообщением:
«Дорогой Славко, я вызываю тебя найти как можно меньшее количество прямоугольников, которые покроют все черные поля. При этом ни одно белое поле не должно быть покрыто прямоугольником, ни одно черное поле не должно быть покрыто двумя или более прямоугольниками, и ни один прямоугольник не должен выходить за пределы доски».
Как вы, вероятно, уже догадались, Славко не справился с задачей, поэтому он попросил вас о помощи.
Входные данные
В первой строке находятся натуральные числа $R$ и $S$, представляющие размеры доски Мирко.
В каждой из следующих $R$ строк содержится по $S$ символов, представляющих поля доски Мирко. Точнее, символ 'B' обозначает белое поле, а символ 'C' обозначает черное поле.
Выходные данные
В каждой из $R$ строк вывода необходимо вывести по $S$ чисел, разделенных пробелом, которые представляют решение задачи Мирко.
Поля, покрытые первым прямоугольником, необходимо отметить в выводе числом 1, поля, покрытые вторым прямоугольником — числом 2, и так далее, вплоть до последнего, $N$-го прямоугольника, чьи покрытые поля отмечаются числом $N$. Поля, не покрытые ни одним прямоугольником (то есть белые поля), необходимо отметить числом 0.
Оценивание
Тестовые примеры, в которых ваше решение нарушает какое-либо из условий задачи, будут оценены в 0 баллов.
Тестовые примеры, в которых ваше решение правильно покрывает все черные поля, но при этом не использует минимальное количество прямоугольников, будут оценены в:
$$0.75 \cdot (A / B)^{10} \cdot X$$
баллов, где $A$ обозначает оптимальное количество прямоугольников, $B$ обозначает количество прямоугольников в вашем решении, а $X$ обозначает количество баллов, которое дает данный тестовый пример.
Разумеется, тестовые примеры, в которых ваше решение правильно покрывает все черные поля с использованием оптимального количества прямоугольников, принесут вам все предусмотренные баллы.
| Тестовые примеры | Количество баллов | Дополнительные ограничения |
|---|---|---|
| 1. – 5. | 25 | $1 \le R, S \le 26$ |
| 6. – 10. | 25 | $1 \le R, S \le 100$ |
| 11. – 15. | 25 | $1 \le R, S \le 250$ |
| 16. – 20. | 25 | $1 \le R, S \le 500$ |
Примеры
Входные данные 1
4 5 CCBCB CCBBB CCCBB CCCBB
Выходные данные 1
1 1 0 2 0 1 1 0 0 0 3 3 3 0 0 3 3 3 0 0
Входные данные 2
7 5 CCCBB BCBBB BCCCB BCCCB CCCCC BBBBB BCCCB
Выходные данные 2
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
Входные данные 3
5 11 BBCCCBCCCBC BCCBCBBCCCC CCCCBCCCCCC BCBCCCBCCCB CCCCBCBBCCB
Выходные данные 3
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