성가신 그림판 도구

면접 대비

시간 제한1초메모리 제한128 MB

요약

목표 흑백 격자와 고정된 r x c 뒤집기 사각형이 주어질 때, 목표에 도달하는 최소 뒤집기 횟수를 구하고 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 시뮬레이션, 구현, 누적 합
정답자: 아직 제출이 없습니다

문제

성가신 그림판 도구가 무엇인지 궁금할 것이다. 우선, 이 그림판 도구는 흑백만 지원한다. 따라서 그림은 검은색 또는 흰색인 픽셀들로 이루어진 직사각형 영역이다. 둘째, 픽셀의 색을 바꾸는 연산은 단 한 가지뿐이다.

그림 안에 완전히 포함되는 $r$ 행 $c$ 열 크기의 직사각형 영역을 하나 고른다. 이 연산의 결과로 선택한 직사각형 안의 모든 픽셀은 색이 반전된다(검은색은 흰색으로, 흰색은 검은색으로).

처음에는 모든 픽셀이 흰색이다. 그림을 만들기 위해 위 연산을 여러 번 적용할 수 있다. 머릿속에 떠올린 특정 그림을 그릴 수 있는가?

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 네 정수 $n$ , $m$ , $r$ , $c$ 가 주어진다( $1 \le r \le n \le 100$ , $1 \le c \le m \le 100$ ). 이어지는 $n$ 개의 줄은 만들고자 하는 그림의 각 행을 나타낸다. $i$ 번째 줄은 완성된 그림에서 $i$ 번째 행의 픽셀 값을 나타내는 $m$ 개의 문자로 이루어진다('0'은 흰색, '1'은 검은색을 뜻한다).

마지막 테스트 케이스 다음에는 네 개의 0으로 이루어진 줄이 온다.

출력

각 테스트 케이스마다 그림을 만드는 데 필요한 최소 연산 횟수를 출력한다. 만들 수 없다면 $-1$ 을 출력한다.

예제3

예제 1

입력

예상 출력

4
6
-1

예제 2
입력
```
2 2 1 1
00
00
0 0 0 0
```
예상 출력
```
0
```
예제 3
입력
```
1 1 1 1
1
0 0 0 0
```
예상 출력
```
1
```