Mirko a trouvé dans la rue une plaque composée de $R \times S$ cases (carrés unitaires) disposées en $R$ lignes et $S$ colonnes. Au moment où Mirko a trouvé la plaque, toutes ses cases étaient blanches. Mirko a décidé de peindre certaines cases en noir. Après avoir fait cela, il a envoyé la plaque à son ami Slavko avec le message suivant :
« Cher Slavko, je te mets au défi de trouver le plus petit nombre possible de rectangles qui recouvriront toutes les cases noires. Ce faisant, aucune case blanche ne doit être recouverte par un rectangle, aucune case noire ne doit être recouverte par deux rectangles ou plus, et aucun rectangle ne doit dépasser des limites de la plaque. »
Comme vous l'avez probablement déjà deviné, Slavko n'est pas à la hauteur du défi et il vous a demandé de l'aide.
Entrée
La première ligne contient les entiers naturels $R$ et $S$ qui représentent les dimensions de la plaque de Mirko.
Dans chacune des $R$ lignes suivantes se trouvent $S$ caractères représentant les cases de la plaque de Mirko. Plus précisément, le caractère 'B' désigne une case blanche et le caractère 'C' désigne une case noire.
Sortie
Dans chacune des $R$ lignes de la sortie, vous devez imprimer $S$ nombres séparés par des espaces qui représentent la solution au défi de Mirko.
Les cases recouvertes par le premier rectangle doivent être marquées avec le nombre 1, les cases recouvertes par le deuxième rectangle doivent être marquées avec le nombre 2, et ainsi de suite jusqu'au dernier, le $N$-ième rectangle, dont les cases recouvertes sont marquées avec le nombre $N$. Les cases qui ne sont recouvertes par aucun rectangle, c'est-à-dire les cases blanches, doivent être marquées avec le nombre 0.
BODOVANJE
Les exemples de test sur lesquels votre solution enfreint l'une des conditions énoncées dans le texte du problème seront notés 0 point.
Les exemples de test sur lesquels votre solution recouvre correctement toutes les cases noires, mais n'utilise pas le nombre minimal de rectangles, seront notés :
$$0.75 \cdot (A / B)^{10} \cdot X$$
points, où $A$ désigne le nombre optimal de rectangles, $B$ désigne le nombre de rectangles dans votre solution, et $X$ désigne le nombre de points attribués à ce test.
Bien entendu, les exemples de test sur lesquels votre solution recouvre correctement toutes les cases noires en utilisant le nombre optimal de rectangles vous rapporteront tous les points prévus.
| testni primjeri | broj bodova | dodatna ograničenja |
|---|---|---|
| 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$ |
Exemples
Entrée 1
4 5 CCBCB CCBBB CCCBB CCCBB
Sortie 1
1 1 0 2 0 1 1 0 0 0 3 3 3 0 0 3 3 3 0 0
Entrée 2
7 5 CCCBB BCBBB BCCCB BCCCB CCCCC BBBBB BCCCB
Sortie 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
Entrée 3
5 11 BBCCCBCCCBC BCCBCBBCCCC CCCCBCCCCCC BCBCCCBCCCB CCCCBCBBCCB
Sortie 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