#/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()