BJ14502 연구소

https://www.acmicpc.net/problem/14502

벽 세 개를 쌓을 수 있는 모든 경우를 찾고, 각 경우마다 바이러스를 BFS로 퍼트려 안전구역의 넓이를 구한다.
각 경우마다 구한 넓이로 최대 안전구역을 갱신한다.

package day0408;
//https://www.acmicpc.net/problem/14502

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class RI {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N, M, numof0 = 0, numof2 = 0, max = 0;
	static int[] numbers = new int[3];
	static int[][] map, tmpmap;
	static ArrayList<int[]> list0;
	static ArrayList<int[]> list2;
	
	static int[][] dir = { { 0, 0, 1, -1 }, { -1, 1, 0, 0 } };

	static void func(int cnt, int start) {
		if (cnt == 3) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					tmpmap[i][j] = map[i][j];
				}
			}
			for(int i = 0; i < 3; i++) {
				int[] xy = list0.get(numbers[i]);
				tmpmap[xy[0]][xy[1]] = 1;
			}
			
			spread();
			return;
		}
		for(int i = start; i < numof0; i++) {
			numbers[cnt] = i;
			func(cnt + 1, i + 1);
		}
	}

	static void spread() {
		Queue<int[]> q = new LinkedList<>();
		for(int i = 0; i < numof2; i++)
			q.add(list2.get(i));
		while (!q.isEmpty()) {
			int[] xy = q.poll();
			int x = xy[0];
			int y = xy[1];
			tmpmap[x][y] = 2;
			for(int d = 0; d < 4; d++) {
				int nx = x + dir[0][d];
				int ny = y + dir[1][d];
				
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || tmpmap[nx][ny] != 0)
					continue;
				q.add(new int[] {nx, ny});
			}
			
		}
		int c = count0();
		if(max < c) max = c;
		
	}

	static int count0() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (tmpmap[i][j] == 0)
					cnt++;
			}
		}
		return cnt;
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		tmpmap = new int[N][M];
		list0 = new ArrayList<>();
		list2 = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0) {
					list0.add(new int[] { i, j });
					numof0++;
				} else if (map[i][j] == 2) {
					list2.add(new int[] { i, j });
					numof2++;
				}
			}
		}
		func(0, 0);
		bw.append(max + "");
		bw.flush();
	}
}