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

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

1018번: 체스판 다시 칠하기

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

 

문제요약

8X8이라는 체스판을 만들어야하고 우리가 크기를 정하는 보드에서 잘라야한다.

그리고 잘라야 할떄 8X8체스판에 맞게 고쳐야하는 최솟값을 구하는 문제이다.

 

문제 포인트

1. 체스판은 총 WB로 시작하는 것과 BW로 시작하는 것 두 개가 있다.

2. 우리가 정한 보드판에서 8X8 체스판 크기를 전부 반복해서 모든 범위 비교해야한다.

#include<iostream>
#include<vector>
#include<cmath>
#include <algorithm>
#define PI 3.1415926535
using namespace std;
char board[201][201];
string WB[8] = {
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
};
string BW[8] = {
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
};
int wb(int x, int y) {                        //체스판이 WB일 경우 틀린값 찾기 x,y는 보드에서의 위치 
    int cnt = 0;
    for (int i = 0; i < 8; i++) {
        for (int k = 0; k < 8; k++) {
            if (board[x + i][y + k] != WB[i][k])
                cnt++;
        }
    }
    return cnt;
}
int bw(int x, int y) {                         //체스판이 WB일 경우 틀린값 찾기 x,y는 보드에서의 위치 
    int cnt = 0;
    for (int i = 0; i < 8; i++) {
        for (int k = 0; k < 8; k++) {
            if (board[x + i][y + k] != BW[i][k])
                cnt++;
        }
    }
    return cnt;
}
int main()
{

    int small;
	int n, m;
	char c;
    int ans;
	cin >> n >> m;
	int cnt = 0;
	for (int i = 0; i < n; i++) {               //보드 값에 값 넣기
        string a;
        cin >> a;
		for (int k = 0; k < m; k++) {
            board[i][k] = a[k];
            
		}
	}
    ans = min(wb(0, 0), bw(0, 0));                    //WB와 BW 중 최솟값
    for (int i = 0; i < n - 7; i++) {
        for (int k = 0; k < m - 7; k++) {
            small = min(wb(i, k), bw(i, k));             //최솟값 비교후 ans에 넣기
            if (ans > small) {
                ans = small;
            }
        }
    }
    cout << ans;
	return 0;
}