[백준][C++] 1080: 행렬

문제 링크: https://www.acmicpc.net/problem/1080

 

그리디 문제입니다.

왼쪽 위부터 다른 칸이 있으면 3x3만큼 뒤집습니다. 3x3만큼 뒤집을 수 있는 칸만 진행합니다.

다 뒤집은 뒤, 모든 배열을 검사해서 안 뒤집어진 칸이 있으면 -1, 아니면 뒤집은 횟수를 출력합니다.

3x3 이하 배열은 못뒤집으니 이 점 체크해줘야 합니다

(저보다 설명 잘돼있는 블로그)

 

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


int diff[50][50];

// (y, x)부터 3x3 뒤집음
inline void flip(int y, int x) {
	for (int i = y; i < y + 3; ++i)
		for (int j = x; j < x + 3; ++j)
			diff[i][j] ^= 1;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			char ch;
			cin >> ch;
			diff[i][j] = (ch=='1');
		}

	bool same = true;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			char ch;
			cin >> ch;
			if (diff[i][j]+'0' != ch)
				same = false;
			diff[i][j] ^= (ch=='1');
		}

	if (same) {
		cout << 0 << '\n';
	}
	else if (n < 3 || m < 3) {
		cout << -1 << '\n';
	}
	else {
		int counter = 0;

		for (int i = 0; i < n - 2; ++i) {
			for (int j = 0; j < m - 2; ++j) {
				if (diff[i][j]) {
					flip(i, j);
					++counter;
				}
			}
		}

		bool ok = true;
		for (int i = 0; i < n && ok; ++i) {
			for (int j = 0; j < m && ok; ++j) {
				if (diff[i][j])
					ok = false;
			}
		}

		cout << (ok ? counter : -1) << '\n';
	}


	return 0;
}