Reflection.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

El granjero Juan tiene un lienzo cuadrado representado por una cuadrícula de N por N celdas. El pinta el lienzo de acuerdo con los siguientes pasos:

  1. Primero, divide el lienzo en cuatro cuadrantes iguales, separados por líneas horizontales y verticales que pasan por el centro del lienzo.
  2. Luego, pinta una hermosa imagen en el cuadrante superior derecho del lienzo. Cada celda de este cuadrante estará pintada (representada por '#') o sin pintar (representada por '.').
  3. Finalmente, como está muy orgulloso de su pintura, la refleja a través de las líneas horizontal y vertical mencionadas anteriormente en los otros cuadrantes del lienzo.

Por ejemplo, supongamos que N=8 y GJ pintó la siguiente imagen en el cuadrante superior derecho en el paso 2:

.#..
.#..
.##.
....

Después de reflejarla a través de las líneas horizontal y vertical en los otros cuadrantes en el paso 3, el lienzo se vería así:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

Sin embargo, mientras GJ dormía, Bessie irrumpió en su granero y robó su preciado lienzo. Lo vandalizó completamente, eliminando algunas celdas pintadas y agregando más celdas pintadas! Antes de que GJ despertara, ella devolvió el lienzo a GJ.

GJ quiere modificar su lienzo para que vuelva a cumplir con la condición de reflexión: es decir, que sea el resultado de reflejar el cuadrante superior derecho en cada uno de los otros cuadrantes. Como solo tiene un número limitado de recursos, le gustaría lograr esto con el menor número de operaciones posible, donde una única operación consiste en pintar una celda o eliminar la pintura de una celda.

Se te proporciona el lienzo después del vandalismo de Bessie, así ­ como una secuencia de U actualizaciones en el lienzo, cada una de las cuales cambia una celda de '.' a '#' o viceversa. Antes de cualquier actualización, y después de cada actualización, debes imprimir el número mínimo de operaciones x que GJ necesita realizar para que se cumpla la condición de reflexión.

Entrada

  • La primera línea contiene los enteros N y U.
  • Las siguientes N líneas contienen N caracteres que representan el lienzo después del vandalismo de Bessie. Cada carácter es '#' o '.'.
  • Las siguientes U líneas contienen enteros r y c, donde 1 \leq r, c \leq N, que representan una actualización en la celda de la r-ésima fila desde la parte superior y la c-ésima columna desde la izquierda del lienzo.

Salida

Imprime U+1 líneas que representan x antes de cualquier actualización y después de cada actualización.

Restricciones

  • 2 \leq N \leq 2000, N es par
  • 0 \leq U \leq 10^5

Ejemplo de Entrada

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

Ejemplo de Salida

4
3
2
1
0
1

El siguiente lienzo satisface la condición de reflexión y difiere del original en 4 operaciones:

....
####
####
....

Es imposible hacer que el lienzo original satisfaga la condición de reflexión con menos de 4 operaciones.

Después de actualizar (1,3), el lienzo se ve así:

....
##.#
####
..##

Ahora se necesitan 3 operaciones para que el lienzo cumpla la condición de reflexión.

Después de actualizar (2,3), el lienzo se ve así:

....
####
####
..##

Ahora se necesitan 2 operaciones para que el lienzo cumpla la condición de reflexión.

USACO 2025 February Contest, Bronze. Problem 1. Reflection.


Comments

There are no comments at the moment.