레이팅 미적용설명
농부 존(Farmer John)의 소들은 인기 게임 "스도쿠"의 흥미로운 변형을 즐겨 한다. 소들의 버전도 일반 스도쿠처럼 3 x 3 부분 격자로 이루어진 9 x 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
이진 스도쿠의 목표는 가능한 한 적은 비트를 뒤집어서, 아홉 개의 행, 아홉 개의 열, 아홉 개의 3 x 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자리 이진 문자열이 주어진다.
출력 형식
모든 행, 열, 부분 격자가 짝수 패리티를 가지게 만들기 위해 필요한 최소 뒤집기 횟수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
bsudoku.in · 출력을 쓸 파일 bsudoku.out예제 1
입력
000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000출력
3설명
Input details: The Sudoku board in the sample input is the same as in the problem text above.
Output details: Three toggles suffice to solve the puzzle.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > November > Gold
태그