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

문제

 

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

1018번: 체스판 다시 칠하기

 

 

풀이

 

8*8 크기의 체스판을 두 개를 준비한다. W로 시작하는 체스판과 B로 시작하는 체스판을 준비한다.

이 두 체스판을 M*N 크기의 보드에 번갈아 가면서 비교해 가면 된다.

 

1. M*N 보드의 왼쪽 끝(0,0)을 기준으로 8*8 크기 만큼 두 개의 체스판과 비교를 한다.

2. 왼쪽 끝을 (0,1), (0,2), ..., (1,0), (1,1), ... 순으로 가능한 범위 내에서 바꿔준 후 8*8 크기 만큼 두 개의 체스판과 비교를 한다.  

3. 비교할 때 마다 비교 횟수를 구한 후 최소값과 비교한다.

 

 

코드

 

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
string board[50];
int N, M;
int result = 987654321;
 
string c1[8] = { "WBWBWBWB", 
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW"};
                
string c2[8] = { "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB"};
 
int check1(int x, int y)
{
    int diff = 0;
    for (int i=x; i<x+8; i++)
        for (int j=y; j<y+8; j++)
            if (board[i][j] != c1[i-x][j-y])
                diff++;
    return diff;
}
 
int check2(int x, int y)
{
    int diff = 0;
    for (int i=x; i<x+8; i++)
        for (int j=y; j<y+8; j++)
            if (board[i][j] != c2[i-x][j-y])
                diff++;
    return diff;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> M;
 
    for (int i=0; i<N; i++)
        cin >> board[i];
 
    for (int i=0; i<=N-8; i++)
        for (int j=0; j<=M-8; j++)
            result = min(result, min(check1(i, j), check2(i,j)));  
       
    cout << result;
 
    return 0;
}