[PS backjun-2.5]1018号:チェス盤を塗り直す

問題情報

白駿1018号-ショートカット

難易度:シルバー5

アルゴリズム:ルーティング転送アルゴリズム

コメント

8×88\times88×チェスのすべての碁盤を8つの大きさのブロックで切り落とし、「W」と「B」の個数までフォークで数え、これらの値の中から最高値を選べばいいのです.
フォーク数の関数はcheckNum()関数で、以下のようになります.

int checkNum(char arr[][8]) {
    int count = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if ((i + j) % 2 == 0) {
                if (arr[i][j] != 'W') count++;
            }
            else {
                if (arr[i][j] != 'B') count++;
            }
        }
    }
    return count;
}

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int checkNum(char arr[][8]) {
    int count = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if ((i + j) % 2 == 0) {
                if (arr[i][j] != 'W') count++;
            }
            else {
                if (arr[i][j] != 'B') count++;
            }
        }
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    
    int m, n;
    cin >> n >> m;
    char c;
    char** arr = new char* [n];
    for (int i = 0; i < n; i++) {
        arr[i] = new char[m];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c;
            arr[i][j] = c;
        }
    }
    int min = 64;
    int max = 0;

    for (int i = 0; i < n-7; i++) {
        for (int j = 0; j < m-7; j++) {
            char temp[8][8];

            for (int a = 0; a < 8; a++) {
                for (int b = 0; b < 8; b++) {
                    temp[a][b] = arr[a + i][b + j];
                }
            }

            int num = checkNum(temp);

            min = min < num ? min : num;
            max = max > num ? max : num;
        }
    }

    cout <<( min > 64 - max ? 64 - max : min);

    for (int i = 0; i < n; i++) {
        delete[] arr[i];
    }
    delete[] arr;
}