행렬 변환
시간 제한2초메모리 제한128 MB
0과 1로 이루어진 두 행렬이 주어질 때, 3x3 부분행렬을 뒤집는 연산으로 A를 B로 만드는 최소 연산 횟수를 구하고 불가능하면 -1을 출력합니다.
문제
0과 1로만 이루어진 두 행렬 A와 B가 있습니다. 한 번의 연산으로 임의의 3×3 부분 행렬을 골라 그 안의 모든 원소를 뒤집을 수 있습니다. 즉 0은 1로, 1은 0으로 바뀝니다.
행렬 A를 행렬 B와 같게 만들기 위해 필요한 최소 연산 횟수를 구하세요.
입력
첫째 줄에 행렬의 크기 N과 M이 주어집니다. N과 M은 50 이하의 자연수입니다.
이어서 N개의 줄에 행렬 A가 주어지고, 그 다음 N개의 줄에 행렬 B가 주어집니다. 각 행은 0과 1로만 이루어진 길이 M의 문자열입니다.
출력
행렬 A를 행렬 B로 바꾸는 데 필요한 최소 연산 횟수를 출력합니다. 불가능하면 -1을 출력합니다.