제출 #920842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920842		sushikid	Tracks in the Snow (BOI13_tracks)	Java	97.81 / 100	2044 ms	603532 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<>();
        cur.add(new int[]{0, 0});
        while(!cur.isEmpty()){
            int[] x = cur.poll();
            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});
                        }
                    }
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int[] e1 : dist){
            for(int e2 : e1){
                if(e2 != Integer.MAX_VALUE){
                    max = Math.max(max, e2);
                }
            }
        }
        pw.println(max);
        pw.close();
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 67.8125 / 70