시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB578840.000%

문제

0과 1로만 이루어져 있는 크기가 N×M인 행렬 A와 B가 주어진다. 교환 연산을 이용해 행렬 A를 B로 바꾸는 최소 연산 횟수을 구하려고 한다. 교환 연산은 행렬 A에서 가로, 세로, 대각선으로 인접한 두 칸을 고르고, 그 값을 서로 교환하는 것이다. 단, 행렬 A의 (i, j)은 최대 Ci,j번 교환 연산에 사용될 수 있다.

입력

첫째 줄에 행렬의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A 정보가 한 줄에 하나씩 주어진다. i번째 줄의 j번째 정수는 행렬 A의 (i, j)에 있는 수 Ai,j를 의미한다. 한 행의 정보는 공백없이 주어진다. 다음 N개의 줄에는 행렬 B의 정보, 그 다음에는 C의 정보가 행렬 A가 주어진 형식과 같게 주어진다.

출력

첫째 줄에 행렬 A를 B로 만들기 위한 최소 연산 횟수를 출력한다. 만약, A를 B로 바꿀 수 없다면 -1을 출력한다.

제한

  • 1 ≤ N, M ≤ 20
  • 0 ≤ Ai,j, Bi,j ≤ 1
  • 0 ≤ Ci,j ≤ 9

예제 입력 1

3 3
110
000
001
000
110
100
222
222
222

예제 출력 1

4

다음과 같이 교환 연산을 사용하면 된다.

  • (0, 0), (1, 1)
  • (0, 1), (1, 0)
  • (2, 2), (2, 1)
  • (2, 1), (2, 0)

예제 입력 2

1 2
10
01
11

예제 출력 2

1

예제 입력 3

3 3
111
000
111
111
000
111
013
537
136

예제 출력 3

0

예제 입력 4

2 3
001
110
000
111
000
111

예제 출력 4

-1

예제 입력 5

2 3
100
000
000
000
999
999

예제 출력 5

-1

예제 입력 6

5 6
011101
110000
000011
000000
100000
110100
000011
000000
110001
000010
305713
537211
352421
242212
333313

예제 출력 6

10

예제 입력 7

2 2
10
00
00
01
11
11

예제 출력 7

1

출처