백준 1018 : 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

1<= n, m <= 50 이므로 완전탐색으로 간단히 해결할 수 있는 문제다.

#include <iostream>
#include <string>

#define min(a,b) a<b?a:b
using namespace std;

int n, m;
int min_val = 1e9;
string board[50];
string c = "BWBWBWBWB";

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> board[i];
}

//flag == 0, start char = 'B'
//flag == 1, start char = 'W'
void checker(int curx, int cury, bool flag) {
	int cnt = 0;
	int cur_idx;
	int cur_start_idx = 0;
	if (flag) cur_start_idx = 1;

	for (int y = cury; y < cury + 8; y++) {
		cur_idx = cur_start_idx;
		for (int x = curx; x < curx + 8; x++) {
			if (board[y][x] != c[cur_idx]) ++cnt;
			++cur_idx;
		}
		cur_start_idx = (cur_start_idx + 1) % 2;
	}

	min_val = min(min_val, cnt);
}

void solution() {
	input();

	for (int y = 0; y <= n - 8; y++) {
		for (int x = 0; x <= m - 8; x++) {
			checker(x, y, 0);
			checker(x, y, 1);
		}
	}

	cout << min_val;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();
}

메모리: 2028 kb

시간: 0 ms