oj.uz

Submission #581660

# Submission time Handle Problem Language Result Execution time Memory
581660 2022-06-23T01:49:15 Z DylanSmith Tracks in the Snow (BOI13_tracks) Java 11
100 / 100
 1175 ms 269020 KB 
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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 13952 KB Output is correct
2 Correct 71 ms 8148 KB Output is correct
3 Correct 62 ms 8600 KB Output is correct
4 Correct 172 ms 12236 KB Output is correct
5 Correct 120 ms 11812 KB Output is correct
6 Correct 65 ms 8148 KB Output is correct
7 Correct 64 ms 8332 KB Output is correct
8 Correct 80 ms 10032 KB Output is correct
9 Correct 99 ms 9596 KB Output is correct
10 Correct 147 ms 11140 KB Output is correct
11 Correct 140 ms 10840 KB Output is correct
12 Correct 119 ms 12076 KB Output is correct
13 Correct 123 ms 12196 KB Output is correct
14 Correct 125 ms 11992 KB Output is correct
15 Correct 149 ms 13744 KB Output is correct
16 Correct 138 ms 13816 KB Output is correct
17 Correct 137 ms 13928 KB Output is correct
18 Correct 196 ms 12280 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 12008 KB Output is correct
2 Correct 240 ms 35112 KB Output is correct
3 Correct 721 ms 269020 KB Output is correct
4 Correct 299 ms 71068 KB Output is correct
5 Correct 497 ms 151592 KB Output is correct
6 Correct 1175 ms 268844 KB Output is correct
7 Correct 131 ms 11092 KB Output is correct
8 Correct 125 ms 12024 KB Output is correct
9 Correct 167 ms 11244 KB Output is correct
10 Correct 149 ms 10436 KB Output is correct
11 Correct 132 ms 11356 KB Output is correct
12 Correct 113 ms 9976 KB Output is correct
13 Correct 241 ms 35184 KB Output is correct
14 Correct 199 ms 25264 KB Output is correct
15 Correct 182 ms 26628 KB Output is correct
16 Correct 164 ms 21376 KB Output is correct
17 Correct 343 ms 76092 KB Output is correct
18 Correct 300 ms 75560 KB Output is correct
19 Correct 276 ms 71024 KB Output is correct
20 Correct 291 ms 64680 KB Output is correct
21 Correct 492 ms 160928 KB Output is correct
22 Correct 524 ms 151740 KB Output is correct
23 Correct 576 ms 136868 KB Output is correct
24 Correct 476 ms 157316 KB Output is correct
25 Correct 955 ms 268680 KB Output is correct
26 Correct 751 ms 208256 KB Output is correct
27 Correct 958 ms 268812 KB Output is correct
28 Correct 1125 ms 268844 KB Output is correct
29 Correct 1114 ms 268928 KB Output is correct
30 Correct 1018 ms 264176 KB Output is correct
31 Correct 858 ms 171836 KB Output is correct
32 Correct 900 ms 268764 KB Output is correct