A las vacas de Farmer John les gusta jugar a una variante interesante del popular juego «Sudoku». Su versión usa una cuadrícula de $9 \times 9$ formada por subcuadrículas de $3 \times 3$, igual que el sudoku normal. Sin embargo, la versión de las vacas solo usa dígitos binarios:
000 000 000 001 000 100 000 000 000 000 110 000 000 111 000 000 000 000 000 000 000 000 000 000 000 000 000
El objetivo del sudoku binario es invertir el menor número posible de bits para que cada una de las nueve filas, nueve columnas y nueve subcuadrículas de $3 \times 3$ tenga paridad par (es decir, contenga un número par de unos). En el ejemplo anterior, un conjunto de 3 inversiones da una solución válida:
000 000 000 001 000 100 001 000 100 000 110 000 000 110 000 000 000 000 000 000 000 000 000 000 000 000 000
Dado el estado inicial de un tablero de sudoku binario, ayuda a las vacas a determinar el número mínimo de inversiones necesarias para resolverlo.
Entrada
- Líneas $1..9$: cada línea contiene una cadena binaria de 9 dígitos correspondiente a una fila del tablero inicial.
Salida
- Línea 1: el número mínimo de inversiones necesarias para que cada fila, columna y subcuadrícula tenga paridad par.
Ejemplos
Entrada 1
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000
Salida 1
3
Nota
El tablero de sudoku de la entrada de ejemplo es el mismo que aparece en el texto del problema anterior.
Tres inversiones bastan para resolver el rompecabezas.
Autor del problema: Brian Dean