문제 번호 5008 --이진 수도쿠(Binary Sudoku)

5008: 이진 수도쿠(Binary Sudoku)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 8  해결 문제 수: 3
[제출][채점상황][게시판][:]

문제 설명

농부존의 소들은 대중에게 인기 있는 게임 중 하나인 수도쿠를 줄긴다.

그 소들이 즐기는 게임은 3*3으로 구성된 9*9격자로 된 버전으로 게임을 진행한다. 이는 일반 수도쿠와 같다.

하지만 이들이 즐기는 수도쿠는 아래와 같이 이진수를 쓴다는 것이 차이가 난다.


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개의 행, 그리고 3*3으로 이루어진 하위 격자판을 모두 짝수패리티로 구성하는 것이다.

(짝수 패리티란 그 영역의 1의 개수가 짝수개가 되도록 한다는 것을 의미한다.)

예를 들면 위 그림에서 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

초기 수도쿠 상태가 주어질 때 조건을 만족하도록 만들 수 있는 최소 뒤집는 횟수를 구하는 프로그램을 작성하시오.

입력

9줄에 걸쳐서 9개의 0과 1이 주어진다

출력

9개의 행, 9개의 열, 9개의 각 3*3영역을 모두 짝수 패리티로 만들 수 있도록 하는 최소 뒤집기 횟수를 출력한다.

입력예시

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

출력예시

3

도움말

출처

[제출][채점상황]