Pythonで理解する蟻本「3-2 Fliptile（POJ No.3279）」(p.141)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-2 Fliptile（POJ No.3279）」(p.141)
のコードをPythonで書き直したものとなっています。

入力

入力例

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

解答

# 隣接するマスの座標
dx = [-1, 0, 0, 0, 1]
dy = [0, -1, 0, 1, 0]

# 入力
M, N = map(int,input().split())
tile = [list(map(int,input().split())) for _ in range(M)]

# (x, y)の色を調べる
def get(x, y):
    c = tile[x][y]
    for d in range(5):
        x2 = x + dx[d]
        y2 = y + dy[d]
        if 0 <= x2 < M and 0 <= y2 < N:
            c += flip[x2][y2]
    return c % 2

# 1行目を決めた場合の最小操作回数を求める
# 解が存在しないならば-1
def calc():
    # 2行目からのひっくり返し方を求める
    for i in range(1, M):
        for j in range(N):
            if get(i - 1, j) != 0:
                # (i - 1, j)が黒色なら、このマスをひっくり返すしかない
                flip[i][j] = 1
    
    # 最後の行が全部白かチェック
    for j in range(N):
        if get(M - 1, j) != 0:
            # 解なし
            return -1
    
    # 反転回数をカウント
    res = 0
    for i in range(M):
        for j in range(N):
            res += flip[i][j]
    return res

res = -1

# 1行目を辞書順で全通り試す
for i in range(1 << N):
    flip = [[0] * N for _ in range(M)]    # 作業用
    for j in range(N):
        flip[0][N - j - 1] = i >> j & 1
    num = calc()
    if num >= 0 and (res < 0 or res > num):
        res = num
        opt = [[flip[i][j] for j in range(N)] for i in range(M)]    # 最適解保存用
    
if res < 0:
    # 解なし
    print('IMPOSSIBLE')
else:
    for i in range(M):
        print(*opt[i])