Submission #581660

#	Time	Username	Problem	Language	Result	Execution time	Memory
581660		DylanSmith	Tracks in the Snow (BOI13_tracks)	Java	100 / 100	1175 ms	269020 KiB

tracks

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);
        }
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70