Submission #920844

#	Time	Username	Problem	Language	Result	Execution time	Memory
920844		sushikid	Tracks in the Snow (BOI13_tracks)	Java	100 / 100	1990 ms	591164 KiB

tracks

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