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 |