행렬 C++ - 백준 1080

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

그리디 문제.

문제 접근

만약 현재 칸을 뒤집어야 한다면 && 뒤집을 수 있다면 뒤집고,

뒤집지 않아도 된다면 뒤집지 않는 알고리즘을 작성했다.

이 값은 최소를 보장할 수 있는데 뒤집는 범위를 다음과 같이 설정했기 때문이다.

현재를 c, 바뀔 칸을 w라 하자.

0 0 0 0 0 0
0 0 c w w 0
0 0 w w w 0
0 0 w w w 0

이렇게 바꾸게 되면, c는 이미 다른 칸들에 의해 바뀌는 것이

끝난 상태여서 다른 칸들에 의해 바뀌지 않는다.

따라서 가능한 경우와 불가능한 경우도 구분이 되고,

뒤집지 않아도 되는 경우를 생각해 최소값도 보장된다.

코드는 다음과 같다.

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

int n,m;
int cnt[50][50];
bool g[50][50];
bool tmp;
bool ansB=true;
int ans=0;
bool f[50][50]; //true -> have to change
                //false -> do not change
int main(){
    memset(cnt,0,sizeof(cnt));
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){scanf("%1d",&g[i][j]);}
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        scanf("%1d",&tmp);
        if(!tmp){
            if(!g[i][j]) f[i][j]=false;
            else f[i][j]=true;
        }
        else{
            if(g[i][j]) f[i][j]=false;
            else f[i][j]=true;
        }
    }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        bool t=false;
        if(cnt[i][j]%2==0 && f[i][j]) t=true;
        else if(cnt[i][j]%2!=0 && !f[i][j]) t=true;
        if(t){
            if(i+2<n && j+2<m){
                for(int h=i;h<i+3;h++) for(int k=j;k<j+3;k++){
                    cnt[h][k]++;
                }
                ans++;
            }
        }
    }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        if(f[i][j] && cnt[i][j]%2==0) ansB=false;
        else if(!f[i][j] && cnt[i][j]%2!=0) ansB=false;
    }
    if(ansB) cout << ans;
    else cout << -1;
}