import java.util.*;
import java.io.*;
public class tracks {
public static void main(String[] args) throws IOException {
Reader in = new Reader();
PrintWriter out = new PrintWriter(System.out);
int N = in.nextInt(), M = in.nextInt();
char[][] mat = new char[N][M];
for (int i = 0; i < N; i++) {
mat[i] = in.next().toCharArray();
}
int[][] dist = new int[N][M];
for (int i = 0; i < N; i++) {
Arrays.fill(dist[i], -1);
}
dist[0][0] = 0;
Deque<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0});
int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
while (!q.isEmpty()) {
int[] current = q.poll();
int r = current[0], c = current[1];
for (int k = 0; k < 4; k++) {
int r2 = r + x[k], c2 = c + y[k];
if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < M) {
if (mat[r2][c2] != '.' && dist[r2][c2] == -1) {
if (mat[r2][c2] == mat[r][c]) {
dist[r2][c2] = dist[r][c];
q.addFirst(new int[]{r2, c2});
} else {
dist[r2][c2] = dist[r][c] + 1;
q.offer(new int[]{r2, c2});
}
}
}
}
}
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
res = Math.max(res, dist[i][j]);
}
}
out.println(res + 1);
out.close();
}
static class Reader {
BufferedInputStream in;
public Reader() {
in = new BufferedInputStream(System.in);
}
public String nextLine() throws IOException {
int c;
StringBuilder sb = new StringBuilder("");
while ((c = in.read()) != '\n')
sb.append((char)(c));
return sb.toString();
}
public String next() throws IOException {
int c;
StringBuilder sb = new StringBuilder("");
while ((c = in.read()) != ' ' && c != '\n')
sb.append((char)(c));
return sb.toString();
}
public int nextInt() throws IOException {
return (int)nextLong();
}
public long nextLong() throws IOException {
int c;
long res = 0;
boolean start = false, negative = false;
while ((c = in.read()) != ' ' && c != '\n' || !start)
if (c >= '0' && c <= '9' || c == '-') {
start = true;
if (c == '-')
negative = true;
else
res = res * 10 + c - '0';
}
return res * (negative ? -1 : 1);
}
}
public static void sort(int[] arr) {
List<Integer> list = new ArrayList<>();
for (int i : arr) {
list.add(i);
}
Collections.sort(list);
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
15084 KB |
Output is correct |
2 |
Correct |
59 ms |
8408 KB |
Output is correct |
3 |
Correct |
66 ms |
8344 KB |
Output is correct |
4 |
Correct |
198 ms |
15248 KB |
Output is correct |
5 |
Correct |
133 ms |
12432 KB |
Output is correct |
6 |
Correct |
59 ms |
8504 KB |
Output is correct |
7 |
Correct |
67 ms |
8264 KB |
Output is correct |
8 |
Correct |
93 ms |
10232 KB |
Output is correct |
9 |
Correct |
102 ms |
9496 KB |
Output is correct |
10 |
Correct |
145 ms |
12668 KB |
Output is correct |
11 |
Correct |
153 ms |
13004 KB |
Output is correct |
12 |
Correct |
147 ms |
13184 KB |
Output is correct |
13 |
Correct |
139 ms |
12496 KB |
Output is correct |
14 |
Correct |
133 ms |
12536 KB |
Output is correct |
15 |
Correct |
163 ms |
14616 KB |
Output is correct |
16 |
Correct |
170 ms |
14704 KB |
Output is correct |
17 |
Correct |
154 ms |
14724 KB |
Output is correct |
18 |
Correct |
187 ms |
15304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
12572 KB |
Output is correct |
2 |
Correct |
263 ms |
25564 KB |
Output is correct |
3 |
Correct |
793 ms |
169572 KB |
Output is correct |
4 |
Correct |
295 ms |
43400 KB |
Output is correct |
5 |
Correct |
617 ms |
99932 KB |
Output is correct |
6 |
Execution timed out |
2057 ms |
367120 KB |
Time limit exceeded |
7 |
Correct |
139 ms |
12564 KB |
Output is correct |
8 |
Correct |
142 ms |
12532 KB |
Output is correct |
9 |
Correct |
175 ms |
12680 KB |
Output is correct |
10 |
Correct |
145 ms |
11164 KB |
Output is correct |
11 |
Correct |
133 ms |
11480 KB |
Output is correct |
12 |
Correct |
133 ms |
10528 KB |
Output is correct |
13 |
Correct |
255 ms |
25560 KB |
Output is correct |
14 |
Correct |
192 ms |
21360 KB |
Output is correct |
15 |
Correct |
197 ms |
20740 KB |
Output is correct |
16 |
Correct |
181 ms |
18020 KB |
Output is correct |
17 |
Correct |
385 ms |
51620 KB |
Output is correct |
18 |
Correct |
349 ms |
50316 KB |
Output is correct |
19 |
Correct |
308 ms |
43660 KB |
Output is correct |
20 |
Correct |
300 ms |
41912 KB |
Output is correct |
21 |
Correct |
539 ms |
104016 KB |
Output is correct |
22 |
Correct |
620 ms |
99856 KB |
Output is correct |
23 |
Correct |
612 ms |
87400 KB |
Output is correct |
24 |
Correct |
561 ms |
101256 KB |
Output is correct |
25 |
Correct |
1018 ms |
169744 KB |
Output is correct |
26 |
Execution timed out |
2123 ms |
550240 KB |
Time limit exceeded |
27 |
Execution timed out |
2025 ms |
358244 KB |
Time limit exceeded |
28 |
Execution timed out |
2039 ms |
367236 KB |
Time limit exceeded |
29 |
Execution timed out |
2111 ms |
350676 KB |
Time limit exceeded |
30 |
Execution timed out |
2047 ms |
370928 KB |
Time limit exceeded |
31 |
Correct |
1184 ms |
119632 KB |
Output is correct |
32 |
Correct |
1657 ms |
307432 KB |
Output is correct |