Algorithm_Practice/2589.java at master · ktyu/Algorithm_Practice · GitHub

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
importjava.io.BufferedReader;
importjava.io.InputStreamReader;
importjava.util.*;

publicclassMain {

staticclassPoint {
intx,y;
Point(intx, inty) {this.x=x; this.y=y;}
 }

publicstaticvoidmain(String[] args) throwsException {

BufferedReaderbr = newBufferedReader(newInputStreamReader(System.in));

StringTokenizerst = newStringTokenizer(br.readLine());
inth = Integer.parseInt(st.nextToken());
intw = Integer.parseInt(st.nextToken());

int[][] map = newint[h][w];

ArrayList<Point> lands = newArrayList<>();

for(inti=0; i<h; i++) {
Stringstr = br.readLine();
for(intj=0; j<w; j++) {
if(str.charAt(j) == 'L') {
map[i][j] = 1;
lands.add(newPoint(i, j));
 }
 }
 }

for(Pointp : lands) {
bfs(map, p);
 }

System.out.println(answer);
 }

staticintanswer = Integer.MIN_VALUE;
staticint[] dx = {1, 0, -1, 0};
staticint[] dy = {0, 1, 0, -1};

staticvoidbfs(int[][] map, Pointstart) {
int[][] cost = newint[map.length][map[0].length];

Queue<Point> q = newLinkedList<>();
q.add(start);
cost[start.x][start.y] = 1;

while(!q.isEmpty()) {
Pointp = q.remove();
answer = Integer.max(answer, cost[p.x][p.y] - 1);

for(inti=0; i<4; i++) {
intx = p.x + dx[i];
inty = p.y + dy[i];

if(x<0 || x>=map.length || y<0 || y>=map[0].length)
continue;

if(cost[x][y] == 0 && map[x][y] == 1) {
cost[x][y] = cost[p.x][p.y] + 1;
q.add(newPoint(x, y));
 }
 }
 }
 }
}