[BOJ 1387] 행렬 교환
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
4
Time limit:
2.0s
Memory limit:
128M
Problem types
Allowed languages
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
3 3
110
000
001
000
110
100
222
222
222예제 출력 1
4예제 입력 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
Comments