-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQ7576.java
More file actions
104 lines (95 loc) ยท 3.16 KB
/
Q7576.java
File metadata and controls
104 lines (95 loc) ยท 3.16 KB
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
/**
* Date: 2018. 9. 1.
* Author: inhyuck | https://github.com/inhyuck
* Solution URL: https://github.com/skhucode/skhucode-inhyuck
* Title: ํ ๋งํ
* Problem: ํ ๋งํ ๋ฅผ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ ๊ฒฉ์๋ชจ์์ ์์๋ค์ ํฌ๊ธฐ์ ์ต์ ํ ๋งํ ๋ค๊ณผ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋,
* ๋ฉฐ์น ์ด ์ง๋๋ฉด ํ ๋งํ ๋ค์ด ๋ชจ๋ ์ต๋์ง, ๊ทธ ์ต์ ์ผ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ.
* URL: https://www.acmicpc.net/problem/7576
*/
package io.inhyuck.graph;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Q7576 {
static int[][] list;
static boolean[][] check;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
list = new int[n][m];
check = new boolean[n][m];
Queue<Tomato> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
list[i][j] = scanner.nextInt();
if (list[i][j] == 1) {
queue.offer(new Tomato(i, j, 0));
check[i][j] = true;
}
}
}
int dayCount = Integer.MIN_VALUE;
int i, j, day;
while (!queue.isEmpty()) {
Tomato tomato = queue.poll();
i = tomato.i;
j = tomato.j;
day = tomato.day;
dayCount = Math.max(day, dayCount);
// System.out.println(tomato.toString() + " | dayCount : " + dayCount);
if (i > 0 && isOk(i - 1, j)) {
insertQueue(queue, i-1, j, day + 1);
}
if (i < n - 1 && isOk(i + 1, j)) {
insertQueue(queue, i+1, j, day + 1);
}
if (j > 0 && isOk(i, j - 1)) {
insertQueue(queue, i, j-1, day + 1);
}
if (j < m - 1 && isOk(i, j + 1)) {
insertQueue(queue, i, j+1, day + 1);
}
}
for (int k = 0; k < n; k++) {
for (int l = 0; l < m; l++) {
if (check[k][l] == false && list[k][l] == 0) {
dayCount = -1;
}
}
}
System.out.println(dayCount);
// System.out.println(Arrays.deepToString(list));
// System.out.println(Arrays.deepToString(check));
}
private static void insertQueue(Queue queue, int i, int j, int day) {
check[i][j] = true;
queue.offer(new Tomato(i, j, day));
}
private static boolean isOk(int i, int j) {
if (list[i][j] == 0 && check[i][j] == false) {
return true;
}
return false;
}
private static class Tomato {
int i;
int j;
int day;
public Tomato(int i, int j, int day) {
this.i = i;
this.j = j;
this.day = day;
}
@Override
public String toString() {
return "Tomato{" +
"i=" + i +
", j=" + j +
", day=" + day +
'}';
}
}
}