//package bfs;
import java.io.*;
import java.util.*;
class tracks {
public static void main(String[] args) throws IOException {
tracks obj = new tracks();
obj.doStuff();
}
private void doStuff() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
char[][] grid = new char[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())];
int[][] vis = new int[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
grid[i] = br.readLine().toCharArray();
}
br.close();
vis[0][0] = 1;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] {0, 0});
int[] yinc = new int[] {-1, 0, 1, 0};
int[] xinc = new int[] {0, 1, 0, -1};
int max = 1;
while (!q.isEmpty()) {
int[] next = q.poll();
char thisChar = grid[next[0]][next[1]];
int thisDist = vis[next[0]][next[1]];
// first is y, second is x
for (int i = 0; i < 4; i++) {
int nexty = next[0]+yinc[i];
int nextx = next[1]+xinc[i];
if (nexty < 0 || nexty >= grid.length) continue;
if (nextx < 0 || nextx >= grid[0].length) continue;
if (vis[nexty][nextx] == 0 && grid[nexty][nextx] != '.') {
if (grid[nexty][nextx] != thisChar) {
vis[nexty][nextx] = thisDist+1;
max = Math.max(max, thisDist+1);
q.add(new int[] {nexty, nextx});
} else {
vis[nexty][nextx] = thisDist;
q.push(new int[] {nexty, nextx});
}
}
}
}
System.out.println(max);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
70 ms |
8548 KB |
Output is correct |
| 3 |
Correct |
76 ms |
8552 KB |
Output is correct |
| 4 |
Correct |
299 ms |
15772 KB |
Output is correct |
| 5 |
Correct |
186 ms |
13152 KB |
Output is correct |
| 6 |
Correct |
71 ms |
8556 KB |
Output is correct |
| 7 |
Correct |
75 ms |
8556 KB |
Output is correct |
| 8 |
Correct |
97 ms |
10340 KB |
Output is correct |
| 9 |
Correct |
101 ms |
10084 KB |
Output is correct |
| 10 |
Correct |
226 ms |
12856 KB |
Output is correct |
| 11 |
Correct |
260 ms |
13172 KB |
Output is correct |
| 12 |
Correct |
193 ms |
14452 KB |
Output is correct |
| 13 |
Correct |
185 ms |
13024 KB |
Output is correct |
| 14 |
Correct |
187 ms |
13168 KB |
Output is correct |
| 15 |
Correct |
237 ms |
16480 KB |
Output is correct |
| 16 |
Correct |
280 ms |
16452 KB |
Output is correct |
| 17 |
Correct |
223 ms |
16096 KB |
Output is correct |
| 18 |
Correct |
264 ms |
15712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
12896 KB |
Output is correct |
| 2 |
Correct |
326 ms |
31864 KB |
Output is correct |
| 3 |
Correct |
856 ms |
213208 KB |
Output is correct |
| 4 |
Correct |
387 ms |
59892 KB |
Output is correct |
| 5 |
Correct |
701 ms |
121568 KB |
Output is correct |
| 6 |
Execution timed out |
2069 ms |
281628 KB |
Time limit exceeded |
| 7 |
Correct |
243 ms |
13164 KB |
Output is correct |
| 8 |
Correct |
192 ms |
13152 KB |
Output is correct |
| 9 |
Correct |
268 ms |
13016 KB |
Output is correct |
| 10 |
Correct |
226 ms |
12256 KB |
Output is correct |
| 11 |
Correct |
193 ms |
12784 KB |
Output is correct |
| 12 |
Correct |
179 ms |
12344 KB |
Output is correct |
| 13 |
Correct |
324 ms |
31696 KB |
Output is correct |
| 14 |
Correct |
264 ms |
23908 KB |
Output is correct |
| 15 |
Correct |
251 ms |
25168 KB |
Output is correct |
| 16 |
Correct |
250 ms |
20064 KB |
Output is correct |
| 17 |
Correct |
501 ms |
64352 KB |
Output is correct |
| 18 |
Correct |
428 ms |
61660 KB |
Output is correct |
| 19 |
Correct |
377 ms |
59740 KB |
Output is correct |
| 20 |
Correct |
350 ms |
54992 KB |
Output is correct |
| 21 |
Correct |
610 ms |
124276 KB |
Output is correct |
| 22 |
Correct |
703 ms |
121672 KB |
Output is correct |
| 23 |
Correct |
771 ms |
109884 KB |
Output is correct |
| 24 |
Correct |
644 ms |
122864 KB |
Output is correct |
| 25 |
Correct |
1136 ms |
213160 KB |
Output is correct |
| 26 |
Correct |
1957 ms |
355652 KB |
Output is correct |
| 27 |
Execution timed out |
2005 ms |
358840 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2047 ms |
281804 KB |
Time limit exceeded |
| 29 |
Correct |
1999 ms |
277280 KB |
Output is correct |
| 30 |
Correct |
1895 ms |
267148 KB |
Output is correct |
| 31 |
Correct |
1500 ms |
144708 KB |
Output is correct |
| 32 |
Correct |
1781 ms |
278792 KB |
Output is correct |
