1080번: 행렬

Memo

• 각 점을 변화 시키기 위해 적어도 한 번은 flip 해주어야 합니다.
• 그 flip의 최소를 구하기 위해서는 0,0 부터 시작하여 x,y를 기준으로 x+2, y+2를 flip시키고, x,y를 N - 2, M - 2 까지 증가해가며 조사해야합니다.
• 이것이 왜 그리디인지 이해가 잘 안되어서 찾아봤는데 매 순간 ‘뒤집어야 하는 칸의 뒤집는 횟수를 최소화한다’는 점에서 그리디 알고리즘으로 분류된다고 합니다. → https://www.acmicpc.net/board/view/13509

Code

제출 날짜

2021/03/18

메모리

2024 KB

시간

0 ms

#include <iostream>

int N, M;
bool A[51][51];
bool B[51][51];
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::string tmp;
	std::cin >> N >> M;
	for (int i = 1 ; i <= N ; i++)
	{
		std::cin >> tmp;
		for (int j = 1 ; j <= tmp.size(); j++)
			A[i][j] = tmp[j - 1] - '0';
	}
	for (int i = 1 ; i <= N ; i++)
	{
		std::cin >> tmp;
		for (int j = 1 ; j <= tmp.size(); j++)
			B[i][j] = tmp[j - 1] - '0';
	}
	ans = 0;
}

bool is_equal()
{
	for (int i = 1 ; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (A[i][j] != B[i][j])
				return (0);
	return (1);
}

void flip(int i, int j)
{
	for (int x = 0 ; x < 3 ; x++)
	{
		for (int y = 0 ; y < 3 ; y++)
		{
			if (A[i + x][j + y])
				A[i + x][j + y] = 0;
			else
				A[i + x][j + y] = 1;
		}
	}
}

void solve()
{
	for (int i = 1 ; i <= N ; i++)
	{
		for (int j = 1 ; j <= M ; j++)
		{
			if (i + 2 > N || j + 2 > M)
				break;
			if (A[i][j] != B[i][j])
			{
				flip(i, j);
				ans++;
			}
		}
	}
	if (!is_equal())
		ans = -1;
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}