D - Domino Covering XOR https://atcoder.jp/contests/abc407/tasks/abc407_d

abc407_d.py

import sys

sys.setrecursionlimit(10**9)


def dfs(i):
    global ans, domino
    if i == H * W:
        score = 0
        for y in range(H):
            for x in range(W):
                if not domino[y * W + x]:
                    score ^= A[y][x]
        ans = max(ans, score)
        return
    
    # ドミノを置かない
    dfs(i + 1)
    y, x = divmod(i, W)    
    # ドミノを横に置く
    if x + 1 < W and not domino[y * W + x] and not domino[y * W + (x + 1)]:
        domino[y * W + x] = domino[y * W + (x + 1)] = True
        dfs(i + 1)
        domino[y * W + x] = domino[y * W + (x + 1)] = False
    # ドミノを縦に置く
    if y + 1 < H and not domino[y * W + x] and not domino[(y + 1) * W + x]:
        domino[y * W + x] = domino[(y + 1) * W + x] = True
        dfs(i + 1)
        domino[y * W + x] = domino[(y + 1) * W + x] = False
    return


H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
domino = [False] * (H * W)
ans = 0
dfs(0)
print(ans)