oj.uz

Submission #789662

# Submission time Handle Problem Language Result Execution time Memory
789662 2023-07-21T16:35:59 Z sushikid Tracks in the Snow (BOI13_tracks) Java 11
100 / 100
 1783 ms 498852 KB 
import java.util.*;
import java.io.*;

public class tracks {
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {-1, 1, 0, 0};
    private static int n, m;

    private static boolean check(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    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());
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            String s = r.readLine();
            for (int j = 0; j < m; j++) {
                grid[i][j] = s.charAt(j);
            }
        }
        int[][] ans = new int[n][m];
        ans[0][0] = 1;
        Deque<int[]> cur = new LinkedList<>();
        cur.add(new int[]{0, 0});
        int z = -1;
        while(!cur.isEmpty()){
            int[] x = cur.poll();
            z = Math.max(z, ans[x[0]][x[1]]);
            for (int i = 0; i < 4; i++) {
                int fx = x[0] + dx[i];
                int fy = x[1] + dy[i];
                if(check(fx, fy) && ans[fx][fy] == 0){
                    if(grid[x[0]][x[1]] == grid[fx][fy]){
                        ans[fx][fy] = ans[x[0]][x[1]];
                        cur.addFirst(new int[]{fx, fy});
                    }
                    else if(grid[fx][fy] != '.'){
                        ans[fx][fy] = ans[x[0]][x[1]] + 1;
                        cur.addLast(new int[]{fx, fy});
                    }
                }
            }
        }
        pw.println(z);
        pw.close();
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 16280 KB Output is correct
2 Correct 52 ms 8156 KB Output is correct
3 Correct 54 ms 8536 KB Output is correct
4 Correct 173 ms 16592 KB Output is correct
5 Correct 127 ms 14044 KB Output is correct
6 Correct 49 ms 8388 KB Output is correct
7 Correct 53 ms 8352 KB Output is correct
8 Correct 67 ms 10424 KB Output is correct
9 Correct 69 ms 10224 KB Output is correct
10 Correct 145 ms 13848 KB Output is correct
11 Correct 145 ms 14048 KB Output is correct
12 Correct 145 ms 14756 KB Output is correct
13 Correct 125 ms 13928 KB Output is correct
14 Correct 125 ms 13996 KB Output is correct
15 Correct 167 ms 15596 KB Output is correct
16 Correct 163 ms 15908 KB Output is correct
17 Correct 149 ms 15676 KB Output is correct
18 Correct 173 ms 16444 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 13412 KB Output is correct
2 Correct 218 ms 27212 KB Output is correct
3 Correct 499 ms 166776 KB Output is correct
4 Correct 239 ms 52248 KB Output is correct
5 Correct 420 ms 109724 KB Output is correct
6 Correct 1650 ms 347284 KB Output is correct
7 Correct 160 ms 13040 KB Output is correct
8 Correct 128 ms 13276 KB Output is correct
9 Correct 168 ms 13872 KB Output is correct
10 Correct 141 ms 12224 KB Output is correct
11 Correct 125 ms 12644 KB Output is correct
12 Correct 125 ms 12164 KB Output is correct
13 Correct 216 ms 27068 KB Output is correct
14 Correct 174 ms 21912 KB Output is correct
15 Correct 166 ms 22720 KB Output is correct
16 Correct 172 ms 18324 KB Output is correct
17 Correct 317 ms 56248 KB Output is correct
18 Correct 267 ms 55536 KB Output is correct
19 Correct 234 ms 51840 KB Output is correct
20 Correct 224 ms 44620 KB Output is correct
21 Correct 381 ms 113044 KB Output is correct
22 Correct 436 ms 109732 KB Output is correct
23 Correct 475 ms 85336 KB Output is correct
24 Correct 393 ms 110904 KB Output is correct
25 Correct 738 ms 166732 KB Output is correct
26 Correct 1783 ms 498852 KB Output is correct
27 Correct 1524 ms 327364 KB Output is correct
28 Correct 1619 ms 347216 KB Output is correct
29 Correct 1684 ms 330868 KB Output is correct
30 Correct 1720 ms 342828 KB Output is correct
31 Correct 863 ms 132048 KB Output is correct
32 Correct 1364 ms 311784 KB Output is correct