Mirko znalazł na ulicy planszę składającą się z $R \times S$ pól (kwadratów jednostkowych), które są rozmieszczone w $R$ wierszach i $S$ kolumnach. W momencie, gdy Mirko znalazł planszę, wszystkie jej pola były wypełnione kolorem białym. Mirko postanowił pomalować niektóre pola na czarno. Po wykonaniu tego zadania wysłał planszę swojemu przyjacielowi Slavko wraz z następującą wiadomością:
„Drogi Slavko, wyzywam cię do znalezienia jak najmniejszej liczby prostokątów, które pokryją wszystkie czarne pola. Przy tym żadne białe pole nie może zostać pokryte prostokątem, żadne czarne pole nie może zostać pokryte dwoma lub większą liczbą prostokątów oraz żaden prostokąt nie może wykraczać poza granice planszy.”
Jak zapewne przypuszczasz, Slavko nie sprostał wyzwaniu, więc poprosił cię o pomoc.
Wejście
W pierwszym wierszu znajdują się liczby naturalne $R$ i $S$, które reprezentują wymiary planszy Mirka.
W każdym z kolejnych $R$ wierszy znajduje się $S$ znaków reprezentujących pola planszy Mirka. Dokładniej, znak 'B' oznacza białe pole, a znak 'C' oznacza czarne pole.
Wyjście
W każdym z $R$ wierszy wyjścia należy wypisać $S$ liczb oddzielonych spacjami, które stanowią rozwiązanie wyzwania Mirka.
Pola pokryte pierwszym prostokątem należy oznaczyć w wyjściu liczbą 1, pola pokryte drugim prostokątem liczbą 2 i tak dalej, aż do ostatniego, $N$-tego prostokąta, którego pola oznacza się liczbą $N$. Pola, które nie są pokryte żadnym prostokątem, czyli pola białe, należy oznaczyć liczbą 0.
Podzadania
Testy, w których twoje rozwiązanie naruszy którykolwiek z warunków zadania, zostaną ocenione na 0 punktów.
Testy, w których twoje rozwiązanie poprawnie pokryje wszystkie czarne pola, ale nie użyje minimalnej liczby prostokątów, zostaną ocenione na:
$$0.75 \cdot (A / B)^{10} \cdot X$$
punktów, gdzie $A$ oznacza optymalną liczbę prostokątów, $B$ oznacza liczbę prostokątów w twoim rozwiązaniu, a $X$ oznacza liczbę punktów przypisanych do danego testu.
Oczywiście testy, w których twoje rozwiązanie poprawnie pokryje wszystkie czarne pola przy użyciu optymalnej liczby prostokątów, przyniosą ci wszystkie przewidziane punkty.
| testy | liczba punktów | dodatkowe ograniczenia |
|---|---|---|
| 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$ |
Przykład
Wejście 1
4 5 CCBCB CCBBB CCCBB CCCBB
Wyjście 1
1 1 0 2 0 1 1 0 0 0 3 3 3 0 0 3 3 3 0 0
Wejście 2
7 5 CCCBB BCBBB BCCCB BCCCB CCCCC BBBBB BCCCB
Wyjście 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
Wejście 3
5 11 BBCCCBCCCBC BCCBCBBCCCC CCCCBCCCCCC BCBCCCBCCCB CCCCBCBBCCB
Wyjście 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