BJ 14502研究所
29556 ワード
https://www.acmicpc.net/problem/14502
3つの壁を積み上げることができるすべての状況を探して、それぞれの状況でウイルスをBFSに伝播して、安全な領域の幅を求めます.
いずれの場合も、求めた幅で最大セキュリティ領域を更新します.
3つの壁を積み上げることができるすべての状況を探して、それぞれの状況でウイルスを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();
}
}
Reference
この問題について(BJ 14502研究所), 我々は、より多くの情報をここで見つけました https://velog.io/@mraz0210/BJ14502-연구소テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol