白駿-14502:研究所[ジャワ]

import java.io.*;
import java.util.*;

public class Main {
	// 바이러스는 상하좌우 인접한 빈 칸으로 모두 퍼져나간다.
	// 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
	// 0은 빈칸, 1은 벽, 2는 바이러스
	static int[] dx = { -1, 0, 1, 0 }; // 상우하좌
	static int[] dy = { 0, 1, 0, -1 };

	static int N, M;
	static int[][] numbers = new int[3][];
	static List<int[]> wall;
	static int max = Integer.MIN_VALUE;
	static int[][] lab;
	static List<int[]> virus = new ArrayList<>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken()); // 세로 크기
		M = Integer.parseInt(st.nextToken()); // 가로 크기

		wall = new ArrayList<int[]>();
		lab = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				lab[i][j] = Integer.parseInt(st.nextToken());
				if (lab[i][j] == 2)
					virus.add(new int[] { i, j });
				if (lab[i][j] == 0) {
					wall.add(new int[] { i, j });
				}
			}
		}
		comb(0, 0);
		System.out.println(max);

	}

	static void bfs(int i, int j, int[][] lab_temp, ArrayDeque<int[]> virus) {
		boolean[][] v = new boolean[N][M];

		while (!virus.isEmpty()) {
			int[] cur = virus.poll();
			for (int k = 0; k < 4; k++) {
				int ni = cur[0] + dx[k];
				int nj = cur[1] + dy[k];
				if (0 <= ni && ni < N && 0 <= nj && nj < M && !v[ni][nj] && lab_temp[ni][nj] == 0) {
					v[ni][nj] = true;
					lab_temp[ni][nj] = 2;
					virus.add(new int[] { ni, nj });
				}
			}
		}
		int count = 0;
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < M; y++) {
				if (lab_temp[x][y] == 0)
					count++;
			}
		}
		max = Math.max(max, count);
	}

	private static void comb(int cnt, int start) {
		if (cnt == 3) { // 세개 뽑으면
			int[][] lab_temp = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					lab_temp[i][j] = lab[i][j];
				}
			}
			for (int i = 0; i < 3; i++) {
				lab_temp[numbers[i][0]][numbers[i][1]] = 1;
			}
			ArrayDeque<int[]> vir = new ArrayDeque<>();
			for (int i = 0; i < virus.size(); i++) {
				vir.offer(virus.get(i));
			}

			bfs(0, 0, lab_temp, vir);
			return;
		}

		for (int i = start; i < wall.size(); i++) { // i : 인덱스
			numbers[cnt] = wall.get(i);
			comb(cnt + 1, i + 1);
		}
	}
}