Mirko encontró en la calle un tablero que consiste en $R \times S$ casillas (cuadrados unitarios) dispuestas en $R$ filas y $S$ columnas. En el momento en que Mirko encontró el tablero, todas sus casillas estaban pintadas de blanco. Mirko decidió pintar algunas casillas de negro. Después de hacerlo, envió el tablero a su amigo Slavko junto con el siguiente mensaje:
"Querido Slavko, te desafío a encontrar el menor número posible de rectángulos que cubran todas las casillas negras. Al hacerlo, ninguna casilla blanca debe ser cubierta por un rectángulo, ninguna casilla negra debe ser cubierta por dos o más rectángulos, y ningún rectángulo debe sobresalir fuera del tablero."
Como probablemente ya sospechas, Slavko no está a la altura del desafío, por lo que te ha pedido ayuda.
Entrada
La primera línea contiene los números naturales $R$ y $S$, que representan las dimensiones del tablero de Mirko.
En cada una de las siguientes $R$ líneas hay $S$ caracteres que representan las casillas del tablero de Mirko. Más precisamente, el carácter 'B' denota una casilla blanca y el carácter 'C' denota una casilla negra.
Salida
En cada una de las $R$ líneas de la salida, es necesario imprimir $S$ números separados por espacios que representen la solución al desafío de Mirko.
Las casillas cubiertas por el primer rectángulo deben marcarse en la salida con el número 1, las casillas cubiertas por el segundo rectángulo deben marcarse con el número 2, y así sucesivamente hasta el último, el $N$-ésimo rectángulo, cuyas casillas cubiertas se marcan con el número $N$. Las casillas que no están cubiertas por ningún rectángulo, es decir, las casillas blancas, deben marcarse con el número 0.
Subtareas
Los casos de prueba en los que tu solución infrinja alguna de las condiciones del enunciado del problema se calificarán con 0 puntos.
Los casos de prueba en los que tu solución cubra correctamente todas las casillas negras, pero no utilice el número mínimo de rectángulos, se calificarán con:
$$0.75 \cdot (A / B)^{10} \cdot X$$
puntos, donde $A$ denota el número óptimo de rectángulos, $B$ denota el número de rectángulos en tu solución, y $X$ denota el número de puntos que otorga dicho caso de prueba.
Por supuesto, los casos de prueba en los que tu solución cubra correctamente todas las casillas negras utilizando el número óptimo de rectángulos te otorgarán todos los puntos previstos.
| Casos de prueba | Puntos | Restricciones adicionales |
|---|---|---|
| 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$ |
Ejemplos
Entrada 1
4 5 CCBCB CCBBB CCCBB CCCBB
Salida 1
1 1 0 2 0 1 1 0 0 0 3 3 3 0 0 3 3 3 0 0
Entrada 2
7 5 CCCBB BCBBB BCCCB BCCCB CCCCC BBBBB BCCCB
Salida 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
Entrada 3
5 11 BBCCCBCCCBC BCCBCBBCCCC CCCCBCCCCCC BCBCCCBCCCB CCCCBCBBCCB
Salida 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