from collections import deque
n, m = map(int, input().split())
maps = []
cctvs = []
for i in range(n):
line = list(map(int, input().split()))
for j, elem in enumerate(line):
if 1 <= elem <= 5:
cctvs.append([elem, i, j])
maps.append(line)
# 각 모든 경우를 고려하면서 사각지대가 가장 최소가 될 때의 크기 출력
dx = [-1, 0, 1, 0, -1] # 시계방향으로 회전
dy = [0, 1, 0, -1, 0]
def watch_cctv(num, x, y, dir, maps):
dir_list = []
if num == 1:
dir_list.append(dir)
elif num == 2:
if dir % 2 == 0:
dir_list.extend([0, 2])
else:
dir_list.extend([1, 3])
elif num == 3:
for i in range(0, 2):
dir_list.append(dir + i)
elif num == 4:
pass_dir = 0
if dir >= 2: # dir - 2만 제외하고 모두 탐색
pass_dir = dir - 2
else:
pass_dir = dir + 2
for i in range(0, 4):
if i == pass_dir:
continue
dir_list.append(i)
else: # num = 5
for i in range(0, 4):
dir_list.append(i)
for d in dir_list:
nx, ny = x + dx[d], y + dy[d]
# 맵을 벗어나거나, 벽(6)을 마주치기 전까지 d 방향으로 일직선으로 계속 탐색
while 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 6:
# 가려는 곳이 빈 공간이라면 7로 표시(CCTV 탐색 영역)
if maps[nx][ny] == 0:
maps[nx][ny] = 7
nx, ny = nx + dx[d], ny + dy[d]
# cctv가 탐색 가능한 모든 방향에 대해 중복순열 구하기
def duplicate_permutation(arr, n):
result = []
def dfs(path):
if len(path) == n:
result.append(path[:])
return
for num in arr:
dfs(path + [num])
dfs([])
return result
all_permu = duplicate_permutation([0, 1, 2, 3], len(cctvs))
min_space = 9999999
# 가능한 모든 경우에 대해서 반복
for i in range(len(all_permu)):
line = all_permu[i]
space = 0
for j in range(len(line)):
# 모든 cctv에 대해 탐색 시작
watch_cctv(cctvs[j][0], cctvs[j][1], cctvs[j][2], line[j], maps)
for j in range(n):
# 맵에서 0인 부분 카운트
space += maps[j].count(0)
# 7로 표기한 부분을 다시 0으로 복구
for k in range(m):
if maps[j][k] == 7:
maps[j][k] = 0
# 최소 사각지대 크기 갱신
min_space = min(min_space, space)
print(min_space)
