시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

N행 M열로 이루어진 행렬 A가 있다. 이때, N과 M은 짝수이며 행렬의 각 원소는 0 또는 1이다.

행렬의 행은 1번부터 N번까지 번호가 매겨져 있으며, 열은 1번부터 M번까지 번호가 매겨져 있다.

팰린드롬이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 문자열을 의미한다. 예를 들어, "1001"과 "0111001110"는 팰린드롬이지만, "1101"과 "000001"은 팰린드롬이 아니다.

행렬 A의 일부 행과 열은 팰린드롬이다. 예를 들어, 아래 행렬 중에서 1번 행과 4번 열은 팰린드롬이다. (1번 행은 "0000", 4번 열은 "0110")

0000
0011
0111
1110

행렬 A와 두 정수 R과 C가 주어진다. 이때, A에서 팰린드롬인 행의 개수가 적어도 R개, 팰린드롬인 열의 개수가 적어도 C개가 되게 하기 위해서 바꿔야 하는 행렬 A의 원소의 개수를 구하는 프로그램을 작성하시오. 원소를 바꾸는 것은 0을 1로, 1을 0으로 바꾸는 것을 의미한다.

입력

첫재 줄에 N과 M, 그리고 R과 C가 주어진다. (2 ≤ N, M ≤ 14, N과 M은 짝수, 0 ≤ R ≤ N, 0 ≤ C ≤ M)

둘째 줄부터 N개의 줄에 행렬 A의 원소가 1행부터 순서대로 주어진다.

출력

첫째 줄에 행렬 A에 팰린드롬인 행의 개수가 적어도 R개, 팰린드롬인 열의 개수가 적어도 C개가 되게 하기 위해서 바꿔야 하는 행렬 A 원소의 개수를 출력한다.

예제 입력 1

4 4 2 2
0000
1000
1100
1110

예제 출력 1

1

예제 입력 2

4 4 3 2
0000
1000
1100
1110

예제 출력 2

3

예제 입력 3

2 2 1 1
01
10

예제 출력 3

1

예제 입력 4

8 8 2 3
01010101
01010101
01010101
01010101
01010101
01010101
01010101
01010101

예제 출력 4

8

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013