oj.uz

Submission #581656

# Submission time Handle Problem Language Result Execution time Memory
581656 2022-06-23T01:36:23 Z DylanSmith Tracks in the Snow (BOI13_tracks) Java 11
86.875 / 100
 2000 ms 550240 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;
        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);
        }
    }
}

Subtask #1
30.0 / 30.0

# 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

Subtask #2
56.875 / 70.0

# 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