그리디를 이용한 문제이다. 풀이는 단순하다. 반복문을 돌면서 배열 A와 B의 현재 위치 값이 다를 경우 현재 위치에서의 3x3만큼 A를 바꿔주면서 횟수를 카운트해주었다.. 그 후 A와 B를 비교한 후 같을 경우 횟수를 출력하고 다를 경우 -1을 출력했다. 이 문제가 왜 그리디인가에 대한 설명은 이 곳에 잘 정리가 되어있다. 그리디 문제가 생각보다 까다로운 것들이 많다. 많이 풀어봐야 겠다.
#include <iostream>
using namespace std;
int N, M;
string A[50];
string B[50];
bool same() {
for (int i = 0; i < N; i++) {
if (A[i] != B[i]) return false;
}
return true;
}
void flip(int y, int x) {
for (int i = y; i < y + 3; i++) {
for (int j = x; j < x + 3; j++) {
A[i][j] = A[i][j] == '0' ? '1' : '0';
}
}
}
void solution() {
int result = 0;
for (int i = 0; i < N - 2; i++) {
for (int j = 0; j < M - 2; j++) {
if (A[i][j] != B[i][j]) {
flip(i, j);
result++;
}
}
}
if (same()) {
cout << result;
}
else {
cout << -1;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N; i++) {
cin >> B[i];
}
solution();
return 0;
}