Коровы Farmer John любят играть в интересный вариант популярной игры «Судоку». Как и обычное судоку, их версия использует сетку $9 \times 9$ с подсетками $3 \times 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
Цель двоичного судоку — инвертировать как можно меньше битов так, чтобы каждая из девяти строк, девяти столбцов и девяти подсеток $3 \times 3$ имела чётную парность (то есть содержала чётное число единиц). Для примера выше набор из 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
По заданному начальному состоянию поля двоичного судоку помогите коровам определить минимальное число инверсий, необходимое для решения.
Входные данные
- Строки $1..9$: каждая строка содержит двоичную строку из 9 цифр, соответствующую одной строке начального поля.
Выходные данные
- Строка 1: минимальное число инверсий, необходимое, чтобы каждая строка, столбец и подсетка имели чётную парность.
Примеры
Входные данные 1
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000
Выходные данные 1
3
Примечание
Поле судоку в примере ввода совпадает с полем в тексте задачи выше.
Для решения головоломки достаточно трёх инверсий.
Автор задачи: Brian Dean