제출 #410882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410882		GhOsT16790	Tracks in the Snow (BOI13_tracks)	Java	84.69 / 100	2100 ms	509604 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 {
        FastIO io = new FastIO();

        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 FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1<<16];
        private int curChar, numChars;

        // standard input
        public FastIO() { this(System.in,System.out); }
        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }
        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }

        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }

        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c; do { c = nextByte(); } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
            return res.toString();
        }
        public int nextInt() { // nextLong() would be implemented similarly
            int c; do { c = nextByte(); } while (c <= ' ');
            int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10*res+c-'0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }
        public double nextDouble() { return Double.parseDouble(next()); }
    }
}

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