Problem 2: Binary Sudoku [Brian Dean]
Коровы Фермера Джона любят играть в интересный вариант популярной игры «Судоку». Их версия включает решетку 9*9, состоящую из подрешеток 3*3, как и обычная Судоку. Однако коровья версия использует только двоичные цифры:
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
Цель этой «Двоичной судоку» – переключить кк можно меньше битов, так чтобы в каждой из 9 строк, в каждом из 9 столбцов, в каждой из 9 подрешеток 3*3 выполнялось свойство «even parity» - то есть содержалось четное количество единиц.
Для примера выше, достаточно сделать 3 переключения, чтобы получить такое решение:
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
По заданному начальному состоянию Двоичной Судоку, определите минимальное количество переключений, чтобы решить ее.
PROBLEM NAME: bsudoku
Формат входных данных
* Строки 1..9: Каждая строка представляет собой 9 символов 0 или 1, задающих начальное положение двоичной судоку.
Формат выходных данных
* Строка 1: Минимальное количество переключений, которые требуется сделать, чтобы стало выполняться свойство «even parity» для всех строк, всех столбцов, и всех подрешеток.
Примечание
Требуется 3 переключения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000
|
3
|