Vlad and Avoiding X (Codeforces 1926F)
Tags: Implement, bitmasks

Vladislav has a grid of size $$$7 \times 7$$$, where each cell is colored black or white. In one operation, he can choose any cell and change its color (black $$$\leftrightarrow$$$ white).Find the minimum number of operations required to ensure that there are no black cells with four diagonal neighbors also being black. The left image shows that initially there are two black cells violating the condition. By flipping one cell, the grid will work. 

Input: The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 200$$$) — the number of test cases. Then follows the description of the test cases.Each test case consists of $$$7$$$ lines, each containing $$$7$$$ characters. Each of these characters is either $$$\texttt{W}$$$ or $$$\texttt{B}$$$, denoting a white or black cell, respectively.

Output: For each test case, output a single integer — the minimum number of operations required to ensure that there are no black cells with all four diagonal neighbors also being black.

Note: The first test case is illustrated in the statement.The second test case is illustrated below:   In the third test case, the grid already satisfies the condition.

Sample Inputs:
4
WWWWWWW
WWWWBBB
WWWWWBW
WWBBBBB
WWWBWWW
WWBBBWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
WBBBBBW
WBBBBBW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
BBBBBBB
BBBBBBB
WWWWWWW
BBBBBBB
BBBBBBB
BBBBBBB

Sample Outputs:
1
2
0
5

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
memo = {}

def solve():
    s = []
    for _ in range(7):
        s.append(input())

    def dfs(state, parity):
        if state == 0:
            return 0
        if (state, parity) in memo:
            return memo[state, parity]
        t = []
        for i in range(7):
            for j in range(7):
                if (i + j) % 2 == parity:
                    data = [0, 0]
                    for (x, y) in [(i - 1, j - 1), (i - 1, j + 1), (i + 1, j - 1), (i + 1, j + 1), (i, j)]:
                        if 0 <= 7 * x + y < 49 and state & 1 << 7 * x + y:
                            data[0] += 1
                            data[1] |= 1 << 7 * x + y
                    if data[0] > 0:
                        t.append(data.copy())
        t.sort(reverse=True)
        res = 212
        for (cnt, cancel) in t:
            res = min(res, 1 + dfs(state ^ cancel, parity))
        memo[state, parity] = res
        return res
    state = [0, 0]
    for i in range(1, 6):
        for j in range(1, 6):
            if s[i][j] == 'B' and s[i - 1][j - 1] == 'B' and (s[i + 1][j - 1] == 'B') and (s[i + 1][j + 1] == 'B') and (s[i - 1][j + 1] == 'B'):
                state[(i + j) % 2] |= 1 << 7 * i + j
    res = dfs(state[0], 0) + dfs(state[1], 1)
    print(res)
    return
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
from itertools import combinations

def ok(g, parity):
    for i in range(1, 6):
        for j in range(1, 6):
            if (i + j) % 2 != parity:
                continue
            if g[i][j] and g[i - 1][j - 1] and g[i - 1][j + 1] and g[i + 1][j - 1] and g[i + 1][j + 1]:
                return False
    return True

def solve():
    g = [[1 if c == 'B' else 0 for c in input()] for _ in range(7)]
    poss0 = [(i, j) for i in range(1, 6) for j in range(1, 6) if (i + j) % 2 == 0 and g[i][j]]
    poss1 = [(i, j) for i in range(1, 6) for j in range(1, 6) if (i + j) % 2 == 1 and g[i][j]]

    def determine(poss, parity):
        for k in range(len(poss) + 1):
            for bb in combinations(poss, k):
                g2 = [row[:] for row in g]
                for (i, j) in bb:
                    g2[i][j] = 0
                if ok(g2, parity):
                    return k
    print(determine(poss0, 0) + determine(poss1, 1))
for _ in range(int(input())):
    solve()

Solution (Python):
from itertools import combinations as q
e = range

def o(g, p):
    for i in e(1, 6):
        for j in e(1, 6):
            if (i + j) % 2 != p:
                continue
            if g[i][j] + g[i - 1][j - 1] + g[i - 1][j + 1] + g[i + 1][j - 1] + g[i + 1][j + 1] == 5:
                return 0
    return 1

def s():
    g = [[1 if c == 'B' else 0 for c in input()] for _ in e(7)]
    a = [(i, j) for i in e(1, 6) for j in e(1, 6) if (i + j) % 2 == 0 and g[i][j]]
    b = [(i, j) for i in e(1, 6) for j in e(1, 6) if (i + j) % 2 == 1 and g[i][j]]

    def d(a, p):
        for k in e(len(a) + 1):
            for b in q(a, k):
                m = [r[:] for r in g]
                for (i, j) in b:
                    m[i][j] = 0
                if o(m, p):
                    return k
    print(d(a, 0) + d(b, 1))
for _ in e(int(input())):
    s()