```
N,M = map(int,input().split())
cctvs,board = [],[]
total_blind = 0
for n in range(N):
line = list(map(int,input().split()))
board.append(line)
for m in range(M):
if 0<line[m]<6:
cctvs.append([line[m],n,m])
if line[m]==0:
total_blind += 1
directions = [[1,0],[0,1],[-1,0],[0,-1]]
cctv_types = {
1: [[0],[1],[2],[3]],
2: [[0,2],[1,3]],
3: [[0,1],[1,2],[2,3],[3,0]],
4: [[0,1,2],[1,2,3],[2,3,0],[3,0,1]],
5: [[0,1,2,3]]
}
for cctv_type, idxs in cctv_types.items():
cctv_types[cctv_type] = [[directions[i] for i in idx] for idx in idxs]
# O(4^8)=O(2^16) 충분
answer = M*N
def dfs(depth):
global answer
if depth == len(cctvs):
count = 0
for line in board:
for i in line:
if i == 0:
count += 1
if answer > count:
answer = count
# print('-----%d------'%answer)
# print(*board,sep='\n')
return
else:
t,x,y = cctvs[depth]
for dirs in cctv_types[t]:
visited = []
for dx,dy in dirs:
nx,ny = x,y
while True:
nx += dx
ny += dy
if 0<=nx<N and 0<=ny<M:
if board[nx][ny] == 6:
break
elif board[nx][ny] == 0:
visited.append([nx,ny])
board[nx][ny] = 7
else:
break
dfs(depth+1)
for nx,ny in visited:
board[nx][ny] = 0
dfs(0)
print(answer)
```