[BOJ] 1018. Repainting the Chessboard

Problem

BOJ 1018. Repainting the Chessboard

Jimin wants to cut an $N \times M$ board into an $8 \times 8$ chessboard. A chessboard must be painted with black and white alternating.

Find the minimum number of squares that have to be repainted.

• $8 \le N, M \le 50$

Input:
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

Output:
12

---

Approach

Could this be solved with a greedy algorithm? What if we decide on the fly whether repainting the current cell is worthwhile?

• It does not work. Leaving the first cell unpainted might be optimal, or painting it might be optimal. You can only tell once the entire $8 \times 8$ pattern is completed.

---

Key Insight

There are only two possible patterns for an $8 \times 8$ chessboard!

1. The case where the top-left starts with white (W)
2. The case where the top-left starts with black (B)

Since the input size is very small at $N, M \le 50$, a Brute Force (exhaustive search) approach is feasible: cut out every possible $8 \times 8$ region and compare it against the two patterns.

---

Step-by-Step Analysis

When $(i, j)$ is taken as the starting point for forming an $8 \times 8$ chessboard:

graph TD
    S["Start at (i, j)"] --> P1["Pattern 1: Top-Left White"]
    S --> P2["Pattern 2: Top-Left Black"]
    
    P1 --> C1{"Count Mismatches"}
    P2 --> C2{"Count Mismatches"}
    
    C1 --> R1["Cost W"]
    C2 --> R2["Cost B"]
    
    R1 --> M["Min(Cost W, Cost B)"]
    R2 --> M
    M --> F["Global Min Update"]

1. Iterate: Loop over starting points $(i, j)$ up to row $N-7$ and column $M-7$.
2. Check: From each starting point, scan inside the $8 \times 8$ region.
3. Count: Verify the expected color from parity relative to the window origin: ((row - i) + (col - j)) % 2.

---

Solution

import sys

# Read input
input = sys.stdin.readline
N, M = map(int, input().split())
board = [input().strip() for _ in range(N)]

min_repaint = float('inf')

# 1. Iterate over every possible 8x8 starting point
for i in range(N - 7):
    for j in range(M - 7):
        cost_start_w = 0
        cost_start_b = 0
        
        # 2. Inspect inside the 8x8 region
        for x in range(i, i + 8):
            for y in range(j, j + 8):
                current_color = board[x][y]
                
                # Use coordinates relative to this 8x8 window so that
                # "starts with W/B" always refers to board[i][j].
                is_even_offset = ((x - i) + (y - j)) % 2 == 0
                
                # Case 1: Start with 'W' (Even offset -> W, Odd offset -> B)
                if is_even_offset:
                    if current_color != 'W': cost_start_w += 1
                    if current_color != 'B': cost_start_b += 1
                else:
                    if current_color != 'B': cost_start_w += 1
                    if current_color != 'W': cost_start_b += 1
                # end if
            # end for
        # end for
        
        min_repaint = min(min_repaint, cost_start_w, cost_start_b)
    # end for
# end for

print(min_repaint)

---

Complexity

• Time Complexity: $O(NM)$
  • Precisely, $(N-7)(M-7) \times 64$ operations.
  • The maximum operation count is $\approx 43 \times 43 \times 64 \approx 120,000$, which is very small.
• Space Complexity: $O(NM)$
  • Storage for the board.

---

Key Takeaways

Point	Description
Brute Force	The most reliable solution when the input size is small
Chessboard Pattern	Use parity relative to the window origin, ((r-start_r)+(c-start_c)) % 2, to check the pattern
Search Space	Explore all $(N-7) \times (M-7)$ sub-chessboards