BOJ 1018 체스판 다시 칠하기

BOJ 1018 체스판 다시 칠하기

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

요약

무작위로 검정색이나 하얀색으로 칠해져있는 MxN크기의 보드를잘라서 8x8 체스판으로 만드는데 색깔을 다시 칠해야하는 횟수를 최소로하려고할때 그 최소횟수를 구하는 문제

풀이

문제에도 주어져있지만 체스판은 두종류가 있다. 첫시작이 검정인것, 하양인것 두종류의 체스판과 비교해서 주어진 보드에서 색깔을 바꿔야하는 것을 다 체크 해둔다음에 8x8로 만들수있는 모든 경우의 수중 체크된수가 가장 작은것을 구하면 된다.

코드

#include<iostream>
#include<string>
using namespace std;
int n, m;
int wstr[55][55], bstr[55][55];
string str[55];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> str[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if ((i + j) % 2 == 0) {
				if (str[i][j] == 'W') {
					bstr[i][j] = 1;
				}
				else if (str[i][j] == 'B') {
					wstr[i][j] = 1;
				}
			}
			else if ((i + j) % 2 == 1) {
				if (str[i][j] == 'B') {
					bstr[i][j] = 1;
				}
				else if (str[i][j] == 'W') {
					wstr[i][j] = 1;
				}
			}
		}
	}
	int cnt1 = 0, cnt2=0, big=1e9;
	for (int i = 0; i <= n-8; i++) {
		for (int j = 0; j <= m - 8; j++) {
			for (int p = i; p < i + 8; p++) {
				for (int q = j; q < j + 8; q++) {
					cnt1 += bstr[p][q];
					cnt2 += wstr[p][q];
				}
			}
			if (big > cnt1) big = cnt1;
			if (big > cnt2) big = cnt2;
			cnt1 = 0;
			cnt2 = 0;
		}
	}
	cout << big << "\n";
}