백준 1018번 (체스판 다시 칠하기) c++

문제

브루트포스를 통해 이문제를 해결하면 된다.

 

먼저, 이렇게 W와 B로 시작하는 체스판을 만들어놓고

string w_start[8] = {

        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
};

string b_start[8] = {

        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
};

 

W와 B로 시작하는 것 중 어떤 것이 더 유리한지 count를 센다.

int w_check(int col, int row){

        int count = 0;
        int w_col = 0;
        int w_row = 0;

        for(register int i = col; i < col + 8; i++){
                w_row = 0;
                for(register int j = row; j < row + 8; j++){
                        if(input[i][j] != w_start[w_col][w_row++]) count++;
                }
                w_col++;
        }

        return count;

}

int b_check(int col, int row){

        int count = 0;
        int b_col = 0;
        int b_row = 0;

        for(register int i = col; i < col + 8; i++){
                b_row = 0;
                for(register int j = row; j < row + 8; j++){
                        if(input[i][j] != b_start[b_col][b_row++]) count++;
                }
                b_col++;
        }

        return count;

}

 

이렇게 두가지 경우를 하나하나 비교해보며 답을 도출하면 된다.

for(register int i = 0; i < N - 7; i++){

                for(register int j = 0; j < M - 7; j++){

                        int temp = min(w_check(i, j), b_check(i, j));

                        if(result > temp) result = temp;

                }

        }

 

#include <bits/stdc++.h>

using namespace std;

char input[51][51];
int N, M;

string w_start[8] = {

        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
};

string b_start[8] = {

        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
};

int w_check(int col, int row){

        int count = 0;
        int w_col = 0;
        int w_row = 0;

        for(register int i = col; i < col + 8; i++){
                w_row = 0;
                for(register int j = row; j < row + 8; j++){
                        if(input[i][j] != w_start[w_col][w_row++]) count++;
                }
                w_col++;
        }

        return count;

}

int b_check(int col, int row){

        int count = 0;
        int b_col = 0;
        int b_row = 0;

        for(register int i = col; i < col + 8; i++){
                b_row = 0;
                for(register int j = row; j < row + 8; j++){
                        if(input[i][j] != b_start[b_col][b_row++]) count++;
                }
                b_col++;
        }

        return count;

}

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        cin >> N >> M;

        for(register int i = 0; i < N; i++){
                for(register int j = 0; j < M; j++){
                        cin >> input[i][j];
                }
        }

        int result = 70;

        for(register int i = 0; i < N - 7; i++){

                for(register int j = 0; j < M - 7; j++){

                        int temp = min(w_check(i, j), b_check(i, j));

                        if(result > temp) result = temp;

                }

        }


        cout << result << '\n';

        return 0;

}