Baekjoon #14502

#include<bits/stdc++.h>
using namespace std;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int a[10][10];
bool vis[10][10];
int N, M;
vector<pair<int,int>> empty_cell;
int ans;

bool valid(int x, int y) {
    return 0<=x && x<N && 0<=y && y<M;
}

void dfs(int idx, int cnt) {
    if(cnt == 3) {
        queue<pair<int,int>> q;
        memset(vis, false, sizeof(vis));
        for(int i=0;i<N;++i) {
            for(int j=0;j<M;++j) {
                if(!vis[i][j] && a[i][j] == 2) {
                    queue<pair<int,int>> q;
                    q.push({i, j});
                    vis[i][j] = true;
                    while(!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
                        for(int k=0;k<4;++k) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(!valid(nx, ny) || vis[nx][ny]) continue;
                            if(a[nx][ny] == 1) continue;
                            vis[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
        int safe = 0;
        for(int i=0;i<N;++i) {
            for(int j=0;j<M;++j) {
                if(!vis[i][j] && a[i][j] == 0) ++safe;
            }
        }
        ans = max(ans, safe);
        return ;
    }
    if(idx == empty_cell.size()) return ;
    int x = empty_cell[idx].first;
    int y = empty_cell[idx].second;
    a[x][y] = 1;
    dfs(idx+1, cnt+1);
    a[x][y] = 0;
    dfs(idx+1, cnt);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=0;i<N;++i) {
        for(int j=0;j<M;++j) {
            cin >> a[i][j];
            if(a[i][j] == 0) empty_cell.emplace_back(i, j);
        }
    }
    dfs(0, 0);
    cout << ans << '\n';
    return 0;
}

import sys
from collections import deque
from itertools import combinations

input = sys.stdin.readline
direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]


def get_pos():
    empty, virus = [], []
    for i in range(n):
        for j in range(m):
            # 비었다면 empty에 추가
            if arr[i][j] == 0:
                empty.append((i, j))
            # 바이러스라면 virus에 추가
            elif arr[i][j] == 2:
                virus.append((i, j))
    return empty, virus


def set_wall(comb):
    for y, x in comb:
        arr[y][x] = 1


def collapse_wall(comb):
    for y, x in comb:
        arr[y][x] = 0


def bfs(virus):
    queue = deque(virus)
    visited = [[False] * m for _ in range(n)]  # 방문 여부
    count = len(virus)  # 바이러스 개수
    while queue:
        q_size = len(queue)
        for _ in range(q_size):
            y, x = queue.popleft()
            visited[y][x] = True  # 방문 처리
            for dy, dx in direction:
                ny, nx = y + dy, x + dx
                # 지도 내에 있고
                if (0 <= ny < n) and (0 <= nx < m):
                    # 빈 공간이고 방문하지 않았다면
                    if arr[ny][nx] == 0 and not visited[ny][nx]:
                        visited[ny][nx] = True  # 방문 처리
                        queue.append((ny, nx))  # 큐에 삽입
                        count += 1  # 바이러스 개수 +1
    return count


# 입력
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

empty, virus = get_pos()  # 빈 위치, 바이러스 위치
combs = combinations(empty, 3)  # 벽을 세울 수 있는 조합

count = int(1e9)  # 바이러스 개수
# 모든 조합에 대해서
for comb in combs:
    # 벽 세우기
    set_wall(comb)

    # 바이러스 전염
    temp = bfs(virus)
    if temp < count:
        count = temp

    # 벽 허물기
    collapse_wall(comb)

# 벽의 개수 계산
wall = n * m - (len(empty) + len(virus))

# 출력
print(n * m - (count + wall + 3))