BOJ 1080 : 행렬

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/1080

 

 

A[r][c] != B[r][c]일 때, 위에서부터 왼쪽으로 A[r][c] ~ A[r + 2][c + 2]까지 뒤집으면 된다.

즉, (r, c)에서는 한 번만 뒤집던가, 뒤집지 않으면 된다. 

(r, c)에서 두 번 이상 뒤집는 것은 원래대로 돌아오기만 하므로 연산의 횟수만 낭비가 된다.

(r, c)를 제외한 3 x 3 좌표는 다음 자기 차례가 올 때, 뒤집을지 판단하면 된다.

#include <stdio.h>

#define MAX (50 + 5)

int N, M;

int A[MAX][MAX];
int B[MAX][MAX];

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%1d", &A[r][c]);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%1d", &B[r][c]);
}

void flip(int sr, int sc)
{
	for (int r = sr; r <= sr + 2; r++)
		for (int c = sc; c <= sc + 2; c++)
			A[r][c] = !A[r][c];
}

int check()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (A[r][c] != B[r][c])
				return 0;

	return 1;
}

int main(void)
{
	input();

	int cnt = 0;
	for (int r = 1; r <= N - 2; r++)
	{
		for (int c = 1; c <= M - 2; c++)
		{
			if (A[r][c] != B[r][c])
			{
				flip(r, c);
				cnt++;
			}
		}
	}

	if (check()) printf("%d\n", cnt);
	else printf("%d\n", -1);
}