/* 문제 : [1080] 행렬
[input]
3 4
0000
0010
0000
1001
1011
1001
[output]
2
[설명]
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한
연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void changeArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2, int x, int y);
bool CompareTwoArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2);
void inputArray(vector<vector<int>> &arr); // 2차원 배열에 데이터 입력
void outputArray(vector<vector<int>> &arr);
int main()
{
int n, m; // 행렬의 크기 n, m
int count = 0; // 연산횟수 누적
bool isEqual = false;
cin >> n >> m;
vector<vector<int>> arr1(n, vector<int>(m, 0));
vector<vector<int>> arr2(n, vector<int>(m, 0));
inputArray(arr1);
inputArray(arr2);
for (int i = 0; i <= (n - 3) && !isEqual; i++) {
for (int k = 0; k <= (m - 3) && !isEqual; k++) {
if (arr1[i][k] == arr2[i][k]) // 바꿀 필요 없으면 패스
continue;
changeArray(arr1, arr2, i, k);
count++;
isEqual = CompareTwoArray(arr1, arr2);
}
}
if (CompareTwoArray(arr1, arr2) == true)
cout << count;
else
cout << "-1";
return 0;
}
bool CompareTwoArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2) {
for (int i = 0, n; i < arr1.size(); i++) {
for (int k = 0; k < arr1[i].size(); k++) {
if (arr1[i][k] != arr2[i][k])
return false;
}
}
return true;
}
void changeArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2, int x, int y) {
for (int i = x; i < (x + 3); i++) { // 3x3범위의 모든 원소 반전 (1->0, 0->1)
for (int k = y; k < (y + 3); k++) {
arr1[i][k] = (1 - arr1[i][k]);
}
}
}
void inputArray(vector<vector<int>> &arr) {
string s;
for (int i = 0, n; i < arr.size(); i++) {
cin >> s;
for (int k = 0; k < arr[i].size(); k++) {
arr[i][k] = s[k] - '0';
}
}
}
void outputArray(vector<vector<int>> &arr) { // 디버깅용
for (int i = 0, n; i < arr.size(); i++) {
for (int k = 0; k < arr[i].size(); k++) {
cout << arr[i][k];
}
cout << endl;
}
}