POJ No.3279(Fliptile)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
#/usr/bin/python3
import sys
BLACK = 1
WHITE = 0
FLIP = 1
# 隣接マスの座標
positions = [{'x':-1, 'y':0}, # 左
{'x':0, 'y':-1}, # 下
{'x':0, 'y':0}, # 中
{'x':0, 'y':1}, # 上
{'x':1, 'y':0}] # 右
def get_color(x, y):
color = problem_matrix[x][y]
for pos in positions:
x2 = x + pos['x']
y2 = y + pos['y']
if 0 <= x2 < M and 0 <= y2 < N:
color += flip_matrix[x2][y2]
# 隣接するマスが反転するため
# (元色 + 隣接マス反転回数) mod 2がマスの色
return color % 2
def calc_flip():
# 1行目は決まっているので2行目から調べる
global flip_matrix
for i in range(1, M):
for j in range(N):
# 一つ前が黒ならヒックリ返すしかない
if get_color(i - 1, j) == BLACK:
flip_matrix[i][j] = FLIP
for j in range(N):
if get_color(M - 1, j) == BLACK:
return -1
counter = 0
for flip_row in flip_matrix:
counter += flip_row.count(FLIP)
return counter
def print_matrix(matrix):
for row in matrix:
line = ''.join([f'{num} ' for num in row]).strip()
print(line)
def solve():
result = -1
global flip_matrix
global opt_matrix
# 一列目のひっくり返しを全パターン(2^N)繰り返す
for i in range(2**N):
flip_matrix = [nums[:] for nums in save_matrix]
for j in range(N):
flip_matrix[0][-j - 1] = i >> j & 1
flip_count = calc_flip()
if flip_count >= 0 and (result < 0 or flip_count < result):
result = flip_count
opt_matrix = [nums[:] for nums in flip_matrix]
if result < 0:
print("IMPOSSIBLE")
sys.exit()
print_matrix(opt_matrix)
M, N = map(int, input().split())
problem_matrix = []
flip_matrix = []
save_matrix = []
opt_matrix = []
for i in range(M):
num_strings = input().split(' ')
problem_matrix.append([int(n) for n in num_strings])
flip_matrix = [[0 for j in range(N)] for i in range(M)]
save_matrix = [nums[:] for nums in flip_matrix]
solve()
Python
INFO