Submission #789662

#	Time	Username	Problem	Language	Result	Execution time	Memory
789662		sushikid	Tracks in the Snow (BOI13_tracks)	Java	100 / 100	1783 ms	498852 KiB

tracks

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 / 30
• Subtask 2: 70 / 70