제출 #410878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410878		GhOsT16790	Tracks in the Snow (BOI13_tracks)	Java	84.69 / 100	2114 ms	517836 KiB

tracks

import java.util.*;
import java.io.*;

public class tracks {
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {-1, 1, 0, 0};
    static int N = 1, H, W;
    static int[][] grid;
    static int[][] count;
    public static void main(String[] args) throws IOException {
        Kattio io = new Kattio();

        H = io.nextInt();
        W = io.nextInt();
        grid = new int[H][W];

        for (int i = 0; i < H; i++) {
            String line = io.next();
            for (int j = 0; j < W; j++) {
                grid[i][j] = (line.charAt(j) == 'F')?1:(line.charAt(j) == 'R')?2:-1;
            }
        }

//        for(int[] row : grid) {
//            for (int col : row) {
//                System.out.print(col + "\t");
//            }
//            System.out.println();
//        }
//        System.out.println();

//        for(int[] row : grid) {
//            for (int col : row) {
//                System.out.print(col + "\t");
//            }
//            System.out.println();
//        }
//        System.out.println();


        io.println(bfs());
        io.close();
    }

    private static int bfs() {
        count = new int[H][W];

        LinkedList<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        count[0][0] = 1;

        while (!q.isEmpty()) {
            Point curr = q.poll();

            N = Math.max(N, count[curr.x][curr.y]);

            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dx[i];
                int ny = curr.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
                if(count[nx][ny] > 0) continue;
                if(grid[nx][ny] == -1) continue;
                if(grid[nx][ny] != grid[curr.x][curr.y]) {
                    count[nx][ny] = count[curr.x][curr.y] + 1;
                    q.addLast(new Point(nx, ny));
                }
                else {
                    count[nx][ny] = count[curr.x][curr.y];
                    q.addFirst(new Point(nx, ny));
                }
            }
        }

        return N;
    }

    private static class Point {
        int x, y;
        public Point(int a, int b) {
            x = a;
            y = b;
        }
        public String toString() {
            return x + " " + y;
        }
    }

    private static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;

        // standard input
        public Kattio() { this(System.in,System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // USACO-style file input
        public Kattio(String problemName) throws IOException {
            super(new FileWriter(problemName+".out"));
            r = new BufferedReader(new FileReader(problemName+".in"));
        }

        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) {}
            return null;
        }

        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }
}

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