Tablero de ajedrez#13093
Se da una tabla de filas y columnas. En cada celda está escrito o .
Hay que eliminar exactamente una fila y exactamente una columna. Después, las filas y columnas restantes se desplazan para que no queden huecos en la tabla. Su orden original se conserva.
A continuación, en una operación se puede cambiar el valor de una celda de a o viceversa.
Hay que obtener una tabla en la que:
en la celda superior izquierda esté escrito ;
dos celdas cualesquiera que compartan un lado contengan números distintos.
Halle la cantidad mínima de tales operaciones, eligiendo de forma óptima la fila y la columna que se eliminan.
La primera línea contiene dos números enteros y (2 \leq n,m \leq 2000) — la cantidad de filas y columnas de la tabla.
Cada una de las siguientes líneas contiene una cadena de longitud formada únicamente por los caracteres y .
Imprima un número entero — la cantidad mínima de operaciones de cambio de valores de las celdas.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el primer ejemplo, al eliminar la segunda fila y la segunda columna queda una tabla con las filas 01 y 10. No es necesario cambiar el valor de ninguna celda.
En el segundo ejemplo, se pueden eliminar la tercera fila y la quinta columna. En la tabla restante basta con cambiar el valor de la celda de la tercera fila y la primera columna de a . Es imposible obtener la tabla requerida sin cambiar el valor de ninguna celda.
En el tercer ejemplo, sin importar qué fila y qué columna se eliminen, queda una celda con el valor . Su valor hay que cambiarlo a .
puntos — n,m \leq 20.
puntos — \min(n,m) \leq 20.
puntos — sin restricciones adicionales.