[Baekjoon,1080] 행렬

문제를 손으로 풀다보면 아래의 두 가지를 깨달을 수 있다.

1. 한 번 뒤집은 구역은 다시 뒤집을 필요가 없다.
2. 뒤집는 순서는 상관 없다.

따라서 좌측 상단의 인덱스부터 하나씩 모든 값을 현재 행렬과 목표 행렬이 다른지 검사하여 다른 경우 뒤집는 연산을 하면 된다. 모든 변환을 마쳤는데 다른 값이 존재하는 경우는 방법이 없는 것이다. 이를 코드로 구현하면 아래와 같다. 코드를 보면 주어지는 행렬이 한 칸씩 띄워서 입력되지 않기 때문에 문자열로 입력 받고있다.

#include <iostream>
#include <vector>
using namespace std;

const int MAX=50;

int n,m;
vector<string> mat, target;

int solve()
{
    int ret=0;
    // 모든 3x3칸을 돌아보며 다른 지점이 있으면 변환 시켜본다. 
    for(int i=0;i<n-2;++i)
        for(int j=0;j<m-2;++j)
            // 다른 지점 발견 
            if(mat[i][j]!=target[i][j])
            {
                ++ret;
                for(int y=0;y<3;++y)
                    for(int x=0;x<3;++x)
                        mat[i+y][j+x]=(mat[i+y][j+x]=='1') ? '0' : '1';
            }
    // 변환 후 다른 지점이 있으면 실패 
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if(mat[i][j]!=target[i][j])
                return -1;
    return ret;
}

int main()
{
    cin>>n>>m;
    mat=target=vector<string>(n);
    for(int i=0;i<n;++i)
        cin>>mat[i];
    for(int i=0;i<n;++i)
        cin>>target[i];
    
    cout<<solve()<<endl;
    return 0;
}