oj.uz

Submission #920844

# Submission time Handle Problem Language Result Execution time Memory
920844 2024-02-03T05:54:44 Z sushikid Tracks in the Snow (BOI13_tracks) Java 11
100 / 100
 1990 ms 591164 KB 
import java.util.*;
import java.io.*;

public class tracks {
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(r.readLine());
        int h = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken());
        int[][] grid = new int[h][w];
        int[][] dist = new int[h][w];
        for (int i = 0; i < h; i++) {
            String s = r.readLine();
            for (int j = 0; j < w; j++) {
                dist[i][j] = Integer.MAX_VALUE;
                if(s.charAt(j) == 'F'){
                    grid[i][j] = 0;
                }
                else if(s.charAt(j) == 'R'){
                    grid[i][j] = 1;
                }
                else{
                    grid[i][j] = 2;
                }
            }
        }
        dist[0][0] = 1;
        LinkedList<int[]> cur = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        cur.add(new int[]{0, 0});
        while(!cur.isEmpty()){
            int[] x = cur.poll();
            max = Math.max(max, dist[x[0]][x[1]]);
            for (int i = 0; i < 4; i++) {
                int fx = x[0] + dx[i];
                int fy = x[1] + dy[i];
                if(0 <= fx && fx < h && 0 <= fy && fy < w && grid[fx][fy] != 2){
                    if(grid[fx][fy] == grid[x[0]][x[1]]){
                        if(dist[x[0]][x[1]] < dist[fx][fy]){
                            dist[fx][fy] = dist[x[0]][x[1]];
                            cur.addFirst(new int[]{fx, fy});
                        }
                    }
                    else{
                        if(dist[x[0]][x[1]] + 1 < dist[fx][fy]){
                            dist[fx][fy] = dist[x[0]][x[1]] + 1;
                            cur.addLast(new int[]{fx, fy});
                        }
                    }
                }
            }
        }
        pw.println(max);
        pw.close();
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 33604 KB Output is correct
2 Correct 55 ms 22368 KB Output is correct
3 Correct 60 ms 28728 KB Output is correct
4 Correct 145 ms 31068 KB Output is correct
5 Correct 130 ms 28676 KB Output is correct
6 Correct 56 ms 22256 KB Output is correct
7 Correct 55 ms 28400 KB Output is correct
8 Correct 77 ms 30380 KB Output is correct
9 Correct 83 ms 23820 KB Output is correct
10 Correct 131 ms 26296 KB Output is correct
11 Correct 138 ms 26372 KB Output is correct
12 Correct 134 ms 27672 KB Output is correct
13 Correct 131 ms 26584 KB Output is correct
14 Correct 135 ms 26876 KB Output is correct
15 Correct 153 ms 29880 KB Output is correct
16 Correct 155 ms 29788 KB Output is correct
17 Correct 143 ms 29696 KB Output is correct
18 Correct 142 ms 29144 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 30372 KB Output is correct
2 Correct 216 ms 46828 KB Output is correct
3 Correct 655 ms 246648 KB Output is correct
4 Correct 277 ms 76976 KB Output is correct
5 Correct 467 ms 154344 KB Output is correct
6 Correct 1990 ms 395272 KB Output is correct
7 Correct 154 ms 26180 KB Output is correct
8 Correct 136 ms 26428 KB Output is correct
9 Correct 171 ms 26104 KB Output is correct
10 Correct 179 ms 25036 KB Output is correct
11 Correct 135 ms 25080 KB Output is correct
12 Correct 123 ms 25352 KB Output is correct
13 Correct 226 ms 46148 KB Output is correct
14 Correct 181 ms 37540 KB Output is correct
15 Correct 173 ms 37156 KB Output is correct
16 Correct 167 ms 33232 KB Output is correct
17 Correct 360 ms 79640 KB Output is correct
18 Correct 300 ms 79168 KB Output is correct
19 Correct 270 ms 75220 KB Output is correct
20 Correct 246 ms 71876 KB Output is correct
21 Correct 436 ms 152540 KB Output is correct
22 Correct 478 ms 146156 KB Output is correct
23 Correct 536 ms 131308 KB Output is correct
24 Correct 458 ms 146804 KB Output is correct
25 Correct 938 ms 236128 KB Output is correct
26 Correct 1698 ms 591164 KB Output is correct
27 Correct 1690 ms 467032 KB Output is correct
28 Correct 1976 ms 394512 KB Output is correct
29 Correct 1965 ms 382332 KB Output is correct
30 Correct 1936 ms 432436 KB Output is correct
31 Correct 1165 ms 163568 KB Output is correct
32 Correct 1489 ms 455016 KB Output is correct