This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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;
int[] q = new int[N * M * 2];
int L = N * M, R = N * M;
int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
int res = 0;
while (L <= R) {
int current = q[L++];
int r = current / M, c = current % M;
res = Math.max(res, dist[r][c]);
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[--L] = r2 * M + c2;
} else {
dist[r2][c2] = dist[r][c] + 1;
q[++R] = r2 * M + c2;
}
}
}
}
}
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |