시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 22 4 4 33.333%

문제

크기가 N*M인 배열 A와 배열 B가 주어진다. 또, 배열 A와 B에는 0과 1로만 이루어져 있다. 세준이는 배열 A를 교환만으로 배열 B로 만드려고 한다. 한 번의 교환은 두 개의 인접한 원소를 바꾸는 것이다. 인접한 것은 수직, 수평, 대각선으로 인접한걸 의미하고 각각의 칸은 총 8개의 인접한 칸을 가지고 있다. (모서리에 있는 칸, 꼭지점에 있는 칸은 제외)

하지만, 교환에 제약이 있는데 (i,j)칸은 총 C[i][j]번만 교환에 이용할 수 있다. 배열 A를 배열 B로 만드는데 드는 교환의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. N과 M은 20보다 작거나 같다. 둘째 줄부터 N개의 줄에 배열 A가 주어지고 그 다음에는 배열 B 그 다음에는 배열 C가 주어진다.. 배열 C의 원소는 0보다 크거나 같고 9보다 작거나 같다.

출력

첫째 줄에 배열 A를 배열 B로 만드는데 드는 교환의 최소값을 출력한다. 만약 바꿀 수 없으면 -1을 출력한다.

예제 입력

3 3
110
000
001
000
110
100
222
222
222

예제 출력

4

힌트

(0,0)-(1,1), (0,1)-(1,0) (2,2)-(2,1), (2,1)-(2,0)

출처