(C++) - 백준(BOJ) 1080번 : 행렬

www.acmicpc.net/problem/1080

1080번: 행렬

greedy문제였습니다.

 

풀이방법

 1. 왼쪽 상단부터 a가 b와 다르다면 a의 해당 위치에 연산함수를 실행합니다. 이렇게 b와 같도록 결정하게 되면 다시 살펴볼 필요가 없습니다. 실행과 함께 ans변수를 ++해줍니다.

 

 2. 행렬 크기만큼 loop를 돌며 만약 a와 b가 서로 다르면 만들 수 없으므로 -1을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int a[51][51],b[51][51],n,m,ans;

void reverseA(int x,int y){
    for(int i = x; i < x + 3; i++){
        for(int j = y; j < y + 3; j++){
            a[i][j] = 1 - a[i][j];
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%1d",&a[i][j]);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%1d",&b[i][j]);

    for(int i = 0; i < n - 2; i++)
        for(int j = 0; j < m - 2; j++)
            if(b[i][j] != a[i][j])
                reverseA(i,j),ans++;
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(a[i][j] != b[i][j]) 
                ans = -1;

    cout << ans <<'\n';
}

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

1 2
0 1
1 1

 

답

-1

 

input

1 2
0 1 
0 1

답

0