yuki_460.py

# -----------------------------------
# yukicoder
# No.460 裏表ちわーわ
# http://yukicoder.me/problems/no/460
# -----------------------------------


# 幅優先探索では遅い!

import copy
m, n = map(int, input().split())
bord = list()
for i in range(m):
	bord.append(list(map(int, input().split())))


def bc(x):
	return [0, 1][x == 0]

def bord_to_str(x):
	s = str()
	for i in x:
		i = [str(j) for j in i]
		s += ''.join(i)
	return s

def str_to_bord(x):
	_bord = [[0 for _ in range(n)] for __ in range(m)]
	for index, i in enumerate(x):
		_bord[index//n][index%n] = int(i)
	return _bord

def check(_bord):
	for row in _bord:
		if sum(row) != 0:
			return False
	return True

def bord_reverse(x, y, _bord):
	tmp_bord = copy.deepcopy(_bord)
	if x != 0:
		if y != 0:
			tmp_bord[x-1][y-1] = bc(tmp_bord[x-1][y-1])
		tmp_bord[x-1][y] = bc(tmp_bord[x-1][y])
		if y != n-1:
			tmp_bord[x-1][y+1] = bc(tmp_bord[x-1][y+1])
	if y != 0:
		tmp_bord[x][y-1] = bc(tmp_bord[x][y-1])
	tmp_bord[x][y] = bc(tmp_bord[x][y])
	if y != n-1:
		tmp_bord[x][y+1] = bc(tmp_bord[x][y+1])
	if x != m-1:
		if y != 0:
			tmp_bord[x+1][y-1] = bc(tmp_bord[x+1][y-1])
		tmp_bord[x+1][y] = bc(tmp_bord[x+1][y])
		if y != n-1:
			tmp_bord[x+1][y+1] = bc(tmp_bord[x+1][y+1])
	return tmp_bord

data = dict()
depth = 0

clear = check(bord)
que = [(bord_to_str(bord), 0)]

while not clear:
	bord, depth = que.pop(0)
	bord = str_to_bord(bord)
	for i in range(m):
		for j in range(n):
			if clear:
				continue
			tmp_bord = bord_reverse(i, j, bord)
			if check(tmp_bord):
				clear = True
			else:
				s = bord_to_str(tmp_bord)
				if s not in data:
					data[s] = True
					que.append((s, depth+1))
	print(depth)

print(depth+1)