import java.io.*;
import java.util.*;
class triple {
public int r;
public int c;
public int depth;
public triple (int r, int c, int depth) {
this.r = r;
this.c = c;
this.depth = depth;
}
public String toString() {
return "(" + r + ", " + c + ", depth: " + depth + ")";
}
}
public class tracks {
public static int H;
public static int W;
public static char[][] snow;
public static int[][] deltas = new int[][] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static void main (String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
snow = new char[H][W];
for (int r = 0; r < H; r++) {
String line = br.readLine();
for (int c = 0; c < W; c++) {
snow[r][c] = line.charAt(c);
}
}
// System.out.println(Arrays.deepToString(snow));
PrintWriter pw = new PrintWriter(System.out);
pw.println(bfs());
pw.close();
}
public static int bfs() {
int numAnimals = 1;
boolean[][] seen = new boolean[H][W];
Deque<triple> frontier = new ArrayDeque<>();
frontier.addFirst(new triple(0, 0, numAnimals));
while (!frontier.isEmpty()) {
triple curTriple = frontier.removeFirst();
int r = curTriple.r;
int c = curTriple.c;
int depth = curTriple.depth;
if (seen[r][c]) {
continue;
}
seen[r][c] = true;
numAnimals = Math.max(numAnimals, depth);
char curAnimal = snow[r][c];
for (int[] delt : deltas) {
int newR = r + delt[0];
int newC = c + delt[1];
if (newR >= 0 && newR < H && newC >= 0 && newC < W) {
if (seen[newR][newC]) {
continue;
}
char newAnimal = snow[newR][newC];
if (newAnimal == 'R' || newAnimal == 'F') {
if (newAnimal == curAnimal) {
frontier.addFirst(new triple(newR, newC, depth));
} else {
frontier.addLast(new triple(newR, newC, depth + 1));
}
}
}
}
}
return numAnimals;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
314 ms |
16168 KB |
Output is correct |
| 2 |
Correct |
72 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
75 ms |
8556 KB |
Output is correct |
| 4 |
Correct |
298 ms |
16848 KB |
Output is correct |
| 5 |
Correct |
197 ms |
13116 KB |
Output is correct |
| 6 |
Correct |
70 ms |
8556 KB |
Output is correct |
| 7 |
Correct |
79 ms |
8544 KB |
Output is correct |
| 8 |
Correct |
104 ms |
10820 KB |
Output is correct |
| 9 |
Correct |
101 ms |
10204 KB |
Output is correct |
| 10 |
Correct |
226 ms |
13280 KB |
Output is correct |
| 11 |
Correct |
271 ms |
14560 KB |
Output is correct |
| 12 |
Correct |
209 ms |
14688 KB |
Output is correct |
| 13 |
Correct |
192 ms |
12896 KB |
Output is correct |
| 14 |
Correct |
194 ms |
12880 KB |
Output is correct |
| 15 |
Correct |
250 ms |
15456 KB |
Output is correct |
| 16 |
Correct |
299 ms |
16096 KB |
Output is correct |
| 17 |
Correct |
238 ms |
15312 KB |
Output is correct |
| 18 |
Correct |
285 ms |
16692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
12740 KB |
Output is correct |
| 2 |
Correct |
337 ms |
19444 KB |
Output is correct |
| 3 |
Correct |
783 ms |
85600 KB |
Output is correct |
| 4 |
Correct |
359 ms |
30944 KB |
Output is correct |
| 5 |
Correct |
627 ms |
57268 KB |
Output is correct |
| 6 |
Execution timed out |
2115 ms |
270304 KB |
Time limit exceeded |
| 7 |
Correct |
258 ms |
12916 KB |
Output is correct |
| 8 |
Correct |
204 ms |
12776 KB |
Output is correct |
| 9 |
Correct |
289 ms |
14176 KB |
Output is correct |
| 10 |
Correct |
234 ms |
12128 KB |
Output is correct |
| 11 |
Correct |
202 ms |
12508 KB |
Output is correct |
| 12 |
Correct |
187 ms |
12128 KB |
Output is correct |
| 13 |
Correct |
333 ms |
19408 KB |
Output is correct |
| 14 |
Correct |
257 ms |
17612 KB |
Output is correct |
| 15 |
Correct |
255 ms |
17616 KB |
Output is correct |
| 16 |
Correct |
273 ms |
16608 KB |
Output is correct |
| 17 |
Correct |
514 ms |
33232 KB |
Output is correct |
| 18 |
Correct |
386 ms |
32720 KB |
Output is correct |
| 19 |
Correct |
357 ms |
31032 KB |
Output is correct |
| 20 |
Correct |
342 ms |
29520 KB |
Output is correct |
| 21 |
Correct |
576 ms |
58228 KB |
Output is correct |
| 22 |
Correct |
614 ms |
57568 KB |
Output is correct |
| 23 |
Correct |
778 ms |
51320 KB |
Output is correct |
| 24 |
Correct |
579 ms |
58080 KB |
Output is correct |
| 25 |
Correct |
943 ms |
85216 KB |
Output is correct |
| 26 |
Execution timed out |
2105 ms |
408948 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2106 ms |
358140 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2084 ms |
270368 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2111 ms |
249728 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2100 ms |
315616 KB |
Time limit exceeded |
| 31 |
Correct |
1677 ms |
68704 KB |
Output is correct |
| 32 |
Execution timed out |
2121 ms |
351120 KB |
Time limit exceeded |
