Problema número 343

Siete de un golpe

Tiempo máximo: 1,000-2,000 sMemoria máxima: 10240 KiB
Matamoscas

En la adaptación libre que hizo Walt Disney del cuento El sastrecillo valiente de los hermanos Grimm un sastre está siendo molestado por siete moscas. La fortuna hace que consiga eliminar las siete de un solo golpe de matamoscas*.

La dificultad de matar de un solo golpe a siete moscas apoyadas en una mesa depende fundamentalmente de tres cosas: el número de moscas que haya en la mesa, el tamaño del matamoscas y lo rápido que éstas sean para levantar el vuelo.

Podemos imaginarnos la mesa dividida en pequeños cuadrados todos del mismo tamaño y que pueden o no tener una mosca dentro. Y podemos tener un matamoscas de tamaño N×M que cuando se coloca sobre la mesa, liquida a todas las moscas que hay en esos N×M cuadrados.

Para ver cómo de extraordinaria es la hazaña del sastre, queremos averiguar en cuántas posiciones podemos colocar el matamoscas sobre la mesa (orientado siempre en horizontal) para matar distintas moscas de un golpe.

Entrada

La entrada estará compuesta por distintos casos de prueba. Cada uno de ellos comienza con una línea con cuatro números: el número de cuadrados en horizontal (tx) y vertical (ty) en los que está dividida la mesa (como mucho 1.000) y el tamaño del matamoscas, o número de cuadrados que cubre en horizontal (1 ≤ mx ≤ tx) y vertical (1 ≤ my ≤ ty). A continuación vienen ty líneas cada una con tx caracteres que indican si en esa celda hay mosca (X) o no (.).

La entrada termina con un tablero y matamoscas de tamaños 0×0, que no debe procesarse.

Salida

Por cada caso de prueba se escribirá una línea con ocho números enteros; el primero de ellos contiene el número de posiciones en donde el matamoscas no mataría ninguna; el siguiente indica las posiciones en las que moriría una única mosca, después dos moscas, y así sucesivamente hasta terminar con el último número que marca las posiciones en las que el sastre mataría a siete moscas de un golpe.

Ten en cuenta que el matamoscas siempre se coloca con la misma orientación y que debe entrar todo entero en la mesa. Además, podría haber posiciones en las que el número de moscas muertas sea superior a siete.

Entrada de ejemplo

3 3 2 2
...
.X.
...
4 3 4 2
X.XX
X.XX
..XX
4 3 3 3
XXX.
XXX.
XXX.
0 0 0 0

Salida de ejemplo

0 4 0 0 0 0 0 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 1 0
1En el cuento original el número de moscas eran "legiones" y, dice, aniquila por lo menos a veinte utilizando un paño. Vemos, pues, que la película de Walt Disney dista mucho del original.