[C/C++] BOJ #1018 - Paint Chess Board Again

The Baekjoon #1018 - Paint Chess Board Again problem requires you to determine the minimum number of squares that need to be repainted on a given rectangular board so that it becomes a valid 8x8 chessboard.

Problem Description:
1. Input:
• A board of size NxM (where N,M > 8).
• Each cell of the board contains either 'W' (white) or 'B' (black).
• A chessboard is valid if:
• Adjacent cells (both horizontally and vertically) have different colors.
• The pattern alternates like a classic chessboard, starting with either 'W' or 'B'.
2. Task:
• Find an 8x8 subsection of the board.
• Determine how many squares need to be repainted in this subsection to make it a valid chessboard.
3. Output:
• The minimum number of repainted squares required for any possible 8x8 subsection.

Key Steps to Solve the Problem:
1. Iterate through all possible  (N - 7)x(M - 7) positions where the top-left corner of an 8x8 chessboard can be placed on the larger board.
2. For each 8x8 subsection:
• Calculate the number of repaints needed to make it match a valid chessboard starting with 'W'.
• Calculate the number of repaints needed to make it match a valid chessboard starting with 'B'.
3. Record the smaller repaint count of the two for each subsection.
4. Return the minimum repaint count among all possible 8x8 subsections.

Example:

Input:

10 13
BBBBBBBBWBWBW
BWBWBWBWBWBWB
BBBBBBBBWBWBW
BWBWBWBWBWBWB
BBBBBBBBWBWBW
BWBWBWBWBWBWB
BBBBBBBBWBWBW
BWBWBWBWBWBWB
BBBBBBBBWBWBW
BWBWBWBWBWBWB

Output:

12

Explanation:
• The given board is 10x13, and we need to extract all possible 8x8 subsections.
• For each subsection, calculate the repaint count to match valid chessboards starting with 'W' and 'B'.
• The smallest repaint count across all subsections is 12.

 

There is a chessboard where black and white squares are arranged without a consistent pattern. A proper chessboard alternates black and white squares in both horizontal and vertical directions. It consists of 8 rows and 8 columns, with 32 black squares and 32 white squares such that squares of the same color are not adjacent to each other. In this problem, the task is to determine the minimum number of squares that need to be repainted to transform the irregular chessboard into a proper chessboard, and calculate the total number of repaints required.

 

Moreover, this chessboard can be larger than 8x8, so you also need to determine the 8x8 section of the board that minimizes the number of repaints.

 

The most brute-force method is to check all colors in every possible 8x8 section of the board to calculate the repaint cost for the minimum number of repaints.  For an 8x8 board, this requires a total of 64 checks. However, for a 15x15 chessboard, this would require a total of 4,096 checks. If the chessboard size is 50x50, as per the problem’s constraints, it would require 78,400 checks.

Honestly, with this level of computation, a simple brute-force solution is perfectly feasible. There haven’t been any reports of time-limit exceeded errors for this problem, and most of the accepted solutions are processed within 0ms. Considering the problem type, a brute-force approach is explicitly suggested. If the problem were one-directional, we might consider writing a more optimized solution.

 

repainting a chessboard

Below is the source code I wrote. Please use it as a reference only.

//----------------------------------------------------------
//    baekjoon #1018 - Paint Chess Board Again.
//        - by Aubrey Choi
//        - created at 2019-06-13
//----------------------------------------------------------
#include <stdio.h>

int count(char board[][50], int x, int y)
{
    int miss = 0;
    for(int i = y; i < y+8; i++)
    {
        for(int j = x; j < x+8; j++)
        {
            if(board[i][j] ^ ((i+j)%2)) miss++;
        }
    }
    return miss >= 32 ? 64-miss : miss;
}

int main()
{
    int m, n;
    char board[50][50];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        char str[100];
        scanf("%s", str);
        for(int j = 0; j < m; j++)
        {
            board[i][j] = (str[j] == 'B');
        }
    }
    int min = 32;
    for(int i = 0; i <= n - 8; i++)
    {
        for(int j = 0; j <= m - 8; j++)
        {
            int s = count(board, j, i);
            if(min > s) min = s;
        }
    }
    printf("%d\n", min);
    return 0;
}