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) {
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 |
320 ms |
18396 KB |
Output is correct |
| 2 |
Correct |
74 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
82 ms |
8688 KB |
Output is correct |
| 4 |
Correct |
332 ms |
18688 KB |
Output is correct |
| 5 |
Correct |
216 ms |
14176 KB |
Output is correct |
| 6 |
Correct |
75 ms |
8556 KB |
Output is correct |
| 7 |
Correct |
81 ms |
8684 KB |
Output is correct |
| 8 |
Correct |
112 ms |
10840 KB |
Output is correct |
| 9 |
Correct |
101 ms |
10284 KB |
Output is correct |
| 10 |
Correct |
235 ms |
14168 KB |
Output is correct |
| 11 |
Correct |
309 ms |
15736 KB |
Output is correct |
| 12 |
Correct |
239 ms |
15708 KB |
Output is correct |
| 13 |
Correct |
220 ms |
14160 KB |
Output is correct |
| 14 |
Correct |
211 ms |
14196 KB |
Output is correct |
| 15 |
Correct |
249 ms |
15964 KB |
Output is correct |
| 16 |
Correct |
313 ms |
18016 KB |
Output is correct |
| 17 |
Correct |
272 ms |
15308 KB |
Output is correct |
| 18 |
Correct |
334 ms |
18808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
13152 KB |
Output is correct |
| 2 |
Correct |
374 ms |
20908 KB |
Output is correct |
| 3 |
Correct |
837 ms |
100576 KB |
Output is correct |
| 4 |
Correct |
413 ms |
35036 KB |
Output is correct |
| 5 |
Correct |
652 ms |
66012 KB |
Output is correct |
| 6 |
Execution timed out |
2065 ms |
334480 KB |
Time limit exceeded |
| 7 |
Correct |
252 ms |
13024 KB |
Output is correct |
| 8 |
Correct |
218 ms |
13152 KB |
Output is correct |
| 9 |
Correct |
347 ms |
14688 KB |
Output is correct |
| 10 |
Correct |
235 ms |
12512 KB |
Output is correct |
| 11 |
Correct |
217 ms |
12768 KB |
Output is correct |
| 12 |
Correct |
182 ms |
12512 KB |
Output is correct |
| 13 |
Correct |
372 ms |
20936 KB |
Output is correct |
| 14 |
Correct |
264 ms |
17880 KB |
Output is correct |
| 15 |
Correct |
254 ms |
18512 KB |
Output is correct |
| 16 |
Correct |
312 ms |
17352 KB |
Output is correct |
| 17 |
Correct |
560 ms |
37520 KB |
Output is correct |
| 18 |
Correct |
421 ms |
35936 KB |
Output is correct |
| 19 |
Correct |
423 ms |
35152 KB |
Output is correct |
| 20 |
Correct |
383 ms |
32732 KB |
Output is correct |
| 21 |
Correct |
612 ms |
67280 KB |
Output is correct |
| 22 |
Correct |
659 ms |
66144 KB |
Output is correct |
| 23 |
Correct |
878 ms |
59520 KB |
Output is correct |
| 24 |
Correct |
592 ms |
66988 KB |
Output is correct |
| 25 |
Correct |
1014 ms |
100704 KB |
Output is correct |
| 26 |
Execution timed out |
2112 ms |
469548 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2075 ms |
464656 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2107 ms |
338476 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2107 ms |
285900 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2074 ms |
346136 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2086 ms |
103956 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2100 ms |
540100 KB |
Time limit exceeded |
