oj.uz

Submission #1059360

# Submission time Handle Problem Language Result Execution time Memory
1059360 2024-08-14T21:50:27 Z silver_moon54 Tracks in the Snow (BOI13_tracks) Java 11
100 / 100
 1267 ms 532808 KB 
import java.io.*;
import java.util.*;

public class tracks {
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {-1, 1, 0, 0};
    static int N = 1, H, W;
    static int[][] grid, count;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        grid = new int[H][W];

        for (int i = 0; i < H; i++) {
            String line = br.readLine();
            for (int j = 0; j < W; j++) {
                grid[i][j] = (line.charAt(j) == 'F') ? 1
                        : (line.charAt(j) == 'R') ? 2
                        : -1;
            }
        }

        br.close();

        pw.println(bfs());
        pw.flush();
    }

    private static int bfs() {
        count = new int[H][W];

        LinkedList<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        count[0][0] = 1;

        while (!q.isEmpty()) {
            int[] curr = q.poll();

            N = Math.max(N, count[curr[0]][curr[1]]);

            for (int i = 0; i < 4; i++) {
                int nx = curr[0] + dx[i];
                int ny = curr[1] + dy[i];

                if (nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
                if (count[nx][ny] > 0) continue;
                if (grid[nx][ny] == -1) continue;
                if (grid[nx][ny] != grid[curr[0]][curr[1]]) {
                    count[nx][ny] = count[curr[0]][curr[1]] + 1;
                    q.addLast(new int[]{nx, ny});
                } else {
                    count[nx][ny] = count[curr[0]][curr[1]];
                    q.addFirst(new int[]{nx, ny});
                }
            }
        }

        return N;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17020 KB Output is correct
2 Correct 40 ms 9036 KB Output is correct
3 Correct 40 ms 9252 KB Output is correct
4 Correct 139 ms 16968 KB Output is correct
5 Correct 99 ms 14524 KB Output is correct
6 Correct 36 ms 8688 KB Output is correct
7 Correct 41 ms 9028 KB Output is correct
8 Correct 55 ms 10520 KB Output is correct
9 Correct 58 ms 10544 KB Output is correct
10 Correct 110 ms 14164 KB Output is correct
11 Correct 120 ms 14224 KB Output is correct
12 Correct 101 ms 15228 KB Output is correct
13 Correct 96 ms 14352 KB Output is correct
14 Correct 100 ms 14176 KB Output is correct
15 Correct 121 ms 16700 KB Output is correct
16 Correct 122 ms 16632 KB Output is correct
17 Correct 115 ms 16300 KB Output is correct
18 Correct 136 ms 16400 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 14440 KB Output is correct
2 Correct 179 ms 34580 KB Output is correct
3 Correct 437 ms 240308 KB Output is correct
4 Correct 203 ms 62168 KB Output is correct
5 Correct 312 ms 132976 KB Output is correct
6 Correct 1267 ms 415460 KB Output is correct
7 Correct 116 ms 12936 KB Output is correct
8 Correct 97 ms 14340 KB Output is correct
9 Correct 127 ms 14560 KB Output is correct
10 Correct 126 ms 12152 KB Output is correct
11 Correct 102 ms 12840 KB Output is correct
12 Correct 89 ms 12224 KB Output is correct
13 Correct 163 ms 34492 KB Output is correct
14 Correct 128 ms 24880 KB Output is correct
15 Correct 128 ms 25504 KB Output is correct
16 Correct 132 ms 21328 KB Output is correct
17 Correct 272 ms 67092 KB Output is correct
18 Correct 223 ms 65872 KB Output is correct
19 Correct 211 ms 61928 KB Output is correct
20 Correct 189 ms 60828 KB Output is correct
21 Correct 314 ms 134912 KB Output is correct
22 Correct 311 ms 132772 KB Output is correct
23 Correct 415 ms 122204 KB Output is correct
24 Correct 317 ms 133380 KB Output is correct
25 Correct 619 ms 239868 KB Output is correct
26 Correct 1173 ms 532808 KB Output is correct
27 Correct 1097 ms 412036 KB Output is correct
28 Correct 1257 ms 415316 KB Output is correct
29 Correct 1253 ms 397604 KB Output is correct
30 Correct 1188 ms 387664 KB Output is correct
31 Correct 699 ms 145996 KB Output is correct
32 Correct 1004 ms 355692 KB Output is correct