Submission #581660

#TimeUsernameProblemLanguageResultExecution timeMemory
581660DylanSmithTracks in the Snow (BOI13_tracks)Java
100 / 100
1175 ms269020 KiB
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...