-
Notifications
You must be signed in to change notification settings - Fork 7
/
Fire3.java
147 lines (128 loc) · 4.94 KB
/
Fire3.java
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
146
147
import java.io.*;
import java.util.*;
public class Fire3 {
public static void main(String[] args) throws IOException {
InputStreamReader inp = new InputStreamReader(System.in);
BufferedReader sc = new BufferedReader(inp);
PrintWriter writer = new PrintWriter(System.out);
String[] rc = sc.readLine().split(" ");
int r = Integer.parseInt(rc[0]);
int c = Integer.parseInt(rc[1]);
int[][] maze = new int[r][c];
int s=0; // Joe
List<Integer> fires = new ArrayList<Integer>(); // Fire
for (int i = 0; i < r; i++) {
String row = sc.readLine();
for (int j = 0; j < c; j++) {
if (row.charAt(j) == '#')
maze[i][j] = 0;
else {
maze[i][j] = 1;
if (row.charAt(j) == 'J')
s = i*c+j;
else if (row.charAt(j) == 'F')
fires.add(i*c+j);
}
}
}
AdjacencyList graph = new AdjacencyList(r*c);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (maze[i][j] == 1) {
if (i > 0 && maze[i-1][j] == 1)
graph.connect(i*c+j,(i-1)*c+j); // up
if (i < r-1 && maze[i+1][j] == 1)
graph.connect(i*c+j,(i+1)*c+j); // down
if (j > 0 && maze[i][j-1] == 1)
graph.connect(i*c+j,i*c+j-1); // left
if (j < c-1 && maze[i][j+1] == 1)
graph.connect(i*c+j,i*c+j+1); // right
}
}
}
graph.doBFS(s); // fill the J array
graph.doBFS(fires); // fill the F array
boolean possible = false;
int minTime = Integer.MAX_VALUE;
for (int i = 0; i < c; i++) {
if (graph.J[i] != Integer.MAX_VALUE && graph.J[i] < graph.F[i]) { // top row
minTime = Math.min(minTime, graph.J[i]);
possible = true;
}
if (graph.J[(r-1)*c+i] != Integer.MAX_VALUE && graph.J[(r-1)*c+i] < graph.F[(r-1)*c+i]) { // bottom row
minTime = Math.min(minTime, graph.J[(r-1)*c+i]);
possible = true;
}
}
for (int i = 0; i < r; i++) {
if (graph.J[i*c] != Integer.MAX_VALUE && graph.J[i*c] < graph.F[i*c]) { // left column
minTime = Math.min(minTime, graph.J[i*c]);
possible = true;
}
if (graph.J[i*c+(c-1)] != Integer.MAX_VALUE && graph.J[i*c+(c-1)] < graph.F[i*c+(c-1)]) { // right column
minTime = Math.min(minTime, graph.J[i*c+(c-1)]);
possible = true;
}
}
if (possible)
writer.println(minTime+1); // extra one step to officially exit the maze
else
writer.println("IMPOSSIBLE");
writer.flush();
}
}
class AdjacencyList {
public List<List<Integer>> list;
public int numVertices;
public int[] J; // for Joe
public int[] F; // for fire
public boolean[] visited;
public AdjacencyList (int V) {
numVertices = V;
list = new ArrayList<List<Integer>>();
for (int i = 0; i < V; i++)
list.add(new ArrayList<Integer>());
J = new int[numVertices]; // Initialize the J array
F = new int[numVertices]; // Initialize the F array
for (int i = 0; i < numVertices; i++) {
J[i] = Integer.MAX_VALUE;
F[i] = Integer.MAX_VALUE;
}
}
public void connect (int a, int b) { list.get(a).add(b); }
public void doBFS (int s) {
J[s] = 0;
visited = new boolean[numVertices];
for (int i = 0; i < numVertices; i++)
visited[i] = false;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(s);
visited[s] = true;
while (!q.isEmpty()) {
Integer u = q.poll();
for (int i = 0; i < list.get(u).size(); i++) {
if (!visited[list.get(u).get(i)]) {
visited[list.get(u).get(i)] = true;
J[list.get(u).get(i)] = J[u] + 1;
q.offer(list.get(u).get(i));
}
}
}
}
public void doBFS (List<Integer> fires) {
Queue<Integer> q = new LinkedList<Integer>();
for (int f : fires) {
F[f] = 0;
q.offer(f);
}
while (!q.isEmpty()) {
Integer u = q.poll();
for (int i = 0; i < list.get(u).size(); i++) {
if (F[list.get(u).get(i)] > F[u] + 1) {
F[list.get(u).get(i)] = F[u] + 1;
q.offer(list.get(u).get(i));
}
}
}
}
}