import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;


class Virus {

int y, x;


public Virus(int y, int x) {

this.y = y;

this.x = x;

}

}


class Wall {

int y, x;


public Wall(int y, int x) {

this.y = y;

this.x = x;

}

}


public class Main {


private static boolean Debug = true;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[][] Visited;

private static ArrayList<Virus> vList;

private static ArrayList<Wall> wList;

private static int MaxSafeCount;

private static int OriginSafeCount;

private static int VirusCount;


public static void main(String[] args) throws Exception {


BufferedReader br;

StringTokenizer st;


if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


// 맵 크기

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


vList = new ArrayList<>();

wList = new ArrayList<>();

OriginSafeCount = 0;

// 맵 읽기

int atom;

Map = new int[MapSize_Y][];

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

atom = Integer.parseInt(st.nextToken());

Map[i][j] = atom;

if (atom == 2) {

vList.add(new Virus(i, j));

OriginSafeCount++;

} else if(atom==0) {

wList.add(new Wall(i, j));

OriginSafeCount++;

}

}

}


MaxSafeCount = 0;

makeWall();

System.out.println(MaxSafeCount);

}


private static void makeWall() {

int wsize = wList.size();


Wall w1, w2, w3;

for (int i = 0; i < wsize; i++) {

for (int j = i + 1; j < wsize; j++) {

for (int k = j + 1; k < wsize; k++) {

w1 = wList.get(i);

w2 = wList.get(j);

w3 = wList.get(k);

Map[w1.y][w1.x] = 1;

Map[w2.y][w2.x] = 1;

Map[w3.y][w3.x] = 1;


simulate();


Map[w1.y][w1.x] = 0;

Map[w2.y][w2.x] = 0;

Map[w3.y][w3.x] = 0;

}

}

}


}


private static void simulate() {


// 조건 초기화

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

Visited[i] = new int[MapSize_X];

}

// log("s:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));


VirusCount = 0;

int y, x;

for (Virus item : vList) {

y = item.y;

x = item.x;


if (Visited[y][x] == 0) {

findPath(y, x);

} else {

// Non-target

}

}


// log("s1:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));

int safeCount = countMap(0);

if (MaxSafeCount < safeCount) {

MaxSafeCount = safeCount;

}


}


static int[] rotY = { 1, 0, -1, 0};

static int[] rotX = { 0, 1, 0, -1};


private static void findPath(int y, int x) {

Visited[y][x] = 1;

VirusCount++;

if(OriginSafeCount - VirusCount < MaxSafeCount) {

// break; 조건

return;

}

int moveY, moveX;

for (int i = 0; i < 4; i++) {


moveY = y + rotY[i];

moveX = x + rotX[i];


if (isRight(moveY, moveX)) {

findPath(moveY, moveX);

}

}


}


private static boolean isRight(int y, int x) {


if (y < 0 || y >= MapSize_Y || x < 0 || x >= MapSize_X) {

return false;

} else if (Visited[y][x] == 1 || Map[y][x] == 1) {

return false;

}


return true;

}


private static int countMap(int what) {


int count = 0;

for (int i = 0; i < MapSize_Y; i++) {

for (int j = 0; j < MapSize_X; j++) {


if (what == 0) { // 빈공간의 수

if (Visited[i][j] == 0 && Map[i][j] == 0) {

count++;

}

} else if (what == 1) { // 벽의 수

if (Map[i][j] == 1) {

count++;

}

} else if (what == 2) { // 바이러스 영역의 수

if (Visited[i][j] == 1 || Map[i][j] == 2) {

count++;

}

}

}

}


return count;

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}


'Knowledge > 알고리즘' 카테고리의 다른 글

백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17
백준: 14503번: 로봇 청소기  (0) 2017.10.17

+ Recent posts