C++ 백준 1080번

백준 1080번 www.acmicpc.net/problem/1080

1080번: 행렬

문제 : 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

 

그러니까 1과 0으로만 이루어진 어떤 행렬 A의 3*3 부분을 정해서 그 안의 수를 1->0, 0->1로 바꾸는데 이 행동을 몇 번 반복하는지의 최솟값을 구하면 된다. 아이디어만 잘 생각하면 어렵지 않은데

예를 들어 5*5크기의 행렬을 생각해보자

이 행렬에서

1

 

저기 맨 위 왼쪽의 1을 0으로 바꾸기 위해서는 

 

이렇게 3*3을 바꾸는거 말고는 방법이 없다.

계속 제일 왼쪽 위를 기준으로 하나씩 옮겨가면서 숫자를 바꾸자.

		1

마지막으로 이 1을 바꿀려면

이렇게 3*3을 바꾸면 되는데 이런 식으로 맨 왼쪽 위를 기준으로 옮기면 더 이상 바꿀 수 있는 숫자가 없다.

결국 저 하얀 부분을 우리가 원하는 행렬이랑 똑같이 만들었을 때 저 파란 부분의 숫자도 같아지면 행렬 A를 행렬B로 바꿀 수 있는거고, 숫자가 다르면 저중에 숫자 하나를 바꾸면 하얀부분의 숫자가 달라지므로 행렬A를 B로 바꿀수 없다.

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
using namespace std;
int a[51][51];
int b[51][51]; // 원하는 행렬
int main() {
	int n, m;
	scanf("%d %d", &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]);
		}
	}
	int ans = 0;
	for (int i = 0; i < n - 2; i++) {
		for (int j = 0; j < m - 2; j++) {
			if (a[i][j] != b[i][j]) {
				for (int k = i; k <= i + 2; k++) {
					for (int l = j; l <= j + 2; l++) {
						a[k][l] = 1 - a[k][l]; // 1이면 0으로, 0이면 1로
					}
				}
				ans += 1;
			}
			else continue;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] != b[i][j]) {
				printf("-1\n");
				return 0;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}