1080 - 행렬

https://www.acmicpc.net/problem/1080

왼쪽에서 오른쪽으로, 위에서 아래로 한 칸씩 확인하면서 3x3크기의 부분행렬이 서로 다르다면 바꾼다. 마지막에 바꾼 횟수를 출력하면 정답이다.

이런 그리디가 통할 수 있는 것은, 이미 지나간 부분(탐색한 부분)에서 서로 다른 칸이 존재하면 안되기 때문이다.

#include <bits/stdc++.h>
using namespace std;

int h, w;
char A[50][51];

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];
        }
    }
}

int main(){
    scanf("%d %d", &h, &w);
    for(int i=0; i<h; ++i) scanf("%s ", A[i]);
    for(int i=0; i<h; ++i){
        char s[51];
        scanf("%s ", s);
        for(int j=0; j<w; ++j){
            A[i][j] = A[i][j] == s[j];
        }
    }
    
    int ans = 0;
    for(int i=0; i<h-2; ++i){
        for(int j=0; j<w-2; ++j){
            if( A[i][j] == 0 ){
                flip(i, j);
                ans += 1;
            }
        }
    }
    
    for(int i=0; i<h; ++i){
        for(int j=0; j<w; ++j)
            if(A[i][j] == 0) return puts("-1"), 0;
    }
    
    printf("%d\n", ans);
    
    return 0;
}