문제

boj1080

  1. A를 B로 바꾸는데 뒤집는 순서는 중요하지 않고, A와 B가 어디가 다른지만 중요하다. 그래서 A와 B가 같은지를 저장하는 bool 배열 check[N][M]를 만들어 현재 A[i][j] == B[i][j]를 저장한다.

  2. 뒤집기를 진행한다. 4중 for문을 돌면서 check의 값을 flip해주면 되는데 check[i][j] != true인 경우에만 flip한다. 그리고 flip할 때마다 count를 증가시킨다. 뒤집을 때는 3*3으로 뒤집으므로 A의 가로 or 세로 크기가 3보다 작은 경우 이 과정을 건너뛴다.

  3. 뒤집기 진행 결과 B를 얻었는지 확인한다. 만약 B와 동일한 행렬이 만들어졌다면 check의 모든 값이 모든 값이 다 true일 것이고, B를 만들 수 없다면 check의 어떤 값은 false일 것이다. 따라서 check에 false 값이 존재하는지 확인해 그렇다면 -1를 출력한다.

구현

#include <iostream>
#include <string>
#include <cstring> // memset
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, M, i, j, k, l, cnt;
	string str;
	char A[51][51];
	bool check[51][51] = { true };

	memset(A, NULL, sizeof(A));
	memset(check, true, sizeof(check));

	cin >> N >> M;

//	1. INPUT
	for (i = 0; i < N; i++) {
		cin >> str;
		for (j = 0; j < M; j++) A[i][j] = str[j];
	}
	for (i = 0; i < N; i++) {
		cin >> str;
		for (j = 0; j < M; j++) {
			if (str[j] != A[i][j]) check[i][j] = false;
		}
	}

// 2. COUNT
	cnt = 0;
	if (N >= 3 && M >= 3) {	
		for (i = 0; i < N - 2; i++) {
			for (j = 0; j < M - 2; j++) {
				if (!check[i][j]) { // flip
					for (k = 0; k < 3; k++) {
						for (l = 0; l < 3; l++) check[i + k][j + l] = !check[i + k][j + l];
					}
					cnt++;
				}
			}
		}	
	}

// 3. CHECK
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				if (!check[i][j]) {
					cout << -1 << endl;
					return 0;
				}
			}
		}
		cout << cnt << endl;
            
	return 0;
}