Đàn bò của Farmer John thích chơi một biến thể thú vị của trò chơi "Sudoku" nổi tiếng. Phiên bản của chúng cũng dùng một lưới \(9 \times 9\) gồm các lưới con \(3 \times 3\), giống như Sudoku thông thường. Tuy nhiên, phiên bản của đàn bò chỉ sử dụng các chữ số nhị phân:

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

Mục tiêu của Sudoku nhị phân là lật ít bit nhất có thể sao cho mỗi hàng trong chín hàng, mỗi cột trong chín cột và mỗi lưới con trong chín lưới con \(3 \times 3\) đều có tính chẵn (tức chứa một số chẵn chữ số 1). Với ví dụ trên, một tập gồm 3 phép lật sẽ cho một lời giải hợp lệ:

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

Cho trạng thái ban đầu của một bảng Sudoku nhị phân, hãy giúp đàn bò xác định số phép lật ít nhất cần thiết để giải bảng đó.

Dữ liệu vào

Mỗi dòng trong 9 dòng chứa một xâu nhị phân gồm 9 chữ số, tương ứng với một hàng của bảng trò chơi ban đầu.

Dữ liệu ra

In số phép lật ít nhất cần thực hiện để mọi hàng, mọi cột và mọi lưới con đều có tính chẵn.

Ví dụ

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

3

Nguồn

USACO 2011 November Contest, Gold Division — Binary Sudoku. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=92