문제
뒤집기 게임의 규칙은 단순하다.
초기에 높이 N, 너비 M크기의 직사각형 모양의 보드에 행과 열을 맞추어 컵을 바로(물을 담을 수 있도록)놓는다.
사회자는 출연자에게 행과 열의 크기 R, C, 그리고 목표로 하는 컵들의 모습을 제시한다. 한 회 뒤집기는 R행 C열의 구간을 모두 뒤집는 것을 말하며, 구간 안의 컵들은 바로 놓인 컵은 거꾸로, 거꾸로 놓인 컵은 바로 뒤집는다.
출연자는 최소의 뒤집기 횟수로 사회자가 제시한 컵들의 모습대로 만들면 된다. 만들 수 없는 경우에는 -1이라고 말한다.
예를 들어 보드 크기가 3, 3이고 사회자가 부른 행과 열의 크기는 2, 1
목표로 하는 모습이
110
010
100
이라고 하자.
0은 컵이 바로 놓인 상태, 1은 거꾸로 놓인 상태이다. 이 경우 출연자는 아래와 같이 3번 만에 과제를 완성할 수 있다.
입력
입력은 10개 이하의 테스트 케이스로 이루어지며 테스트 케이스의 마지막은 0 0 0 0이 입력된다.
각 테스트 케이스의 첫 행에는 보드의 높이를 나타내는 N, 너비를 나타내는 M, 그리고 사회자가 부르는 행과 열의 범위를 나타내는 R, C가 주어진다. (1 ≤ R ≤ N ≤ 100) (1 ≤ C ≤ M ≤ 100)
다음 행부터 N개의 행에 걸쳐 목표로 하는 과제가 주어진다.
0은 컵이 바로 놓인 상태 1은 거꾸로 놓인 상태이다.
출력
컵의 초기상태(모두 바로 놓인 상태)에서 조건에 맞추어 목표로 하는 상태로 만들 때 최소 뒤집기 회수를 출력한다.
테스트 케이스 0 0 0 0인 경우는 출력하지 않는다.
만들 수 없는 경우 -1을 출력한다.
예제
3 3 1 1
010
101
010
4 3 2 1
011
110
011
110
3 4 2 2
0110
0111
0000
0 0 0 0
4
6
-1
로그인해야 코드를 작성할 수 있어요.