Baekjoon-14502-연구소

from collections import deque
import sys
input = sys.stdin.readline

N,M = map(int, input().split())
board = []
viruses = []
empties = []
for n in range(N):
    line = list(map(int,input().split()))
    board.append(line)
    for m in range(M):
        if line[m] == 0:
            empties.append([n,m])
        elif line[m] == 2:
            viruses.append([n,m])

def bfs():
    visited = [[0] * M for _ in range(N)]
    q = deque(viruses)
    for x,y in viruses:
        visited[x][y] = 1
    count = 0
    while q:
        x,y = q.popleft()
        for dx,dy in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx,ny = x+dx, y+dy
            if 0<=nx<N and 0<=ny<M and visited[nx][ny]==0 and board[nx][ny]==0:
                visited[nx][ny] = 1
                q.append([nx,ny])
                count += 1
                if count >= min_polute:
                    return min_polute+1
    return count

# Brute-force -> O(64^5)=O(2^30) -> 너무 크지 않나...?
min_polute = len(empties)
min_walls = []
for i in range(len(empties)-2):
    board[empties[i][0]][empties[i][1]] = 1
    for j in range(i+1, len(empties)-1):
        board[empties[j][0]][empties[j][1]] = 1
        for k in range(j+1, len(empties)):
            board[empties[k][0]][empties[k][1]] = 1
            min_polute = min(bfs(),min_polute)
            board[empties[k][0]][empties[k][1]] = 0
        board[empties[j][0]][empties[j][1]] = 0
    board[empties[i][0]][empties[i][1]] = 0
print(len(empties)-min_polute-3)