|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
private static int N;
private static int M;
private static int[][] map;
private static ArrayList<Pos> virusPos;
private static int result;
private static int[] dx = { 0, 1, 0, -1 };
private static int[] dy = { 1, 0, -1, 0 };
private static boolean check;
private static Pos[] set;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken()); // 바이러스 놓을 수 있는 수
map = new int[N][N];
virusPos = new ArrayList<Pos>();
set = new Pos[M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) {
map[i][j] = 0;
virusPos.add(new Pos(i, j));
}
if(map[i][j] == 1) map[i][j] = -1;
}
}
result = Integer.MAX_VALUE;
check = false;
combination(0, 0);
if(result == Integer.MAX_VALUE) System.out.println("-1");
else System.out.println(result);
}// end of main
public static void combination(int k, int len) {
if (len == M) {
process();
return;
} else {
combination(i + 1, len + 1);
}
}
}
public static void process() {
Queue<Pos> queue = new LinkedList<Pos>();
int[][] temp = new int[N][N];
boolean[][] visited = new boolean[N][N];
for (int i = 0; i < temp.length; i++) {
System.arraycopy(map[i], 0, temp[i], 0, N);
}
for (int i = 0; i < set.length; i++) {
temp[set[i].x][set[i].y] = -2;
visited[set[i].x][set[i].y] = true;
queue.add(new Pos(set[i].x, set[i].y));
}
// print(temp);
int value = 1;
while (!queue.isEmpty()) {
for (int i = 0; i < size; i++) {
Pos p = queue.poll();
for (int j = 0; j < dx.length; j++) {
int nx = p.x + dx[j];
int ny = p.y + dy[j];
if(nx >=0 && ny >=0 && nx < N && ny < N && map[nx][ny] !=-1 && !visited[nx][ny]) {
visited[nx][ny] = true;
temp[nx][ny] = value;
queue.add(new Pos(nx, ny));
}
}
}
value++;
}
// print(temp);
int time = 0;
label :for (int j = 0; j < temp.length; j++) {
for (int i = 0; i < temp.length; i++) {
if(temp[i][j] == 0) {
check = false;
break label;
}else {
if(time < temp[i][j]) time = temp[i][j];
check = true;
}
}
}
if(check) {
result = result > time ? time :result;
}
else return;
}
private static void print(int[][] temp) {
// TODO Auto-generated method stub
for (int i = 0; i < temp.length; i++) {
for (int j = 0; j < temp.length; j++) {
System.out.print(temp[i][j]);
}
System.out.println();
}
System.out.println("========================");
}
static class Pos {
int x;
int y;
public Pos(int x, int y) {
super();
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Pos [x=" + x + ", y=" + y + "]";
}
}
}// end of class
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'Algorithm 문제풀이 > simulation' 카테고리의 다른 글
| [BOJ] 백준 17142-연구소3(java) (0) | 2019.09.01 |
|---|---|
| [BOJ] 백준 17144-미세먼지안녕(java) (0) | 2019.09.01 |
| [BOJ] 백준 17143-낚시왕(java) (0) | 2019.08.29 |
| [BOJ] 백준 16236-아기상어(JAVA) (0) | 2019.08.29 |
| [BOJ] 백준 14501- 퇴사(JAVA) (0) | 2019.08.16 |