Submission #1059360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059360		silver_moon54	Tracks in the Snow (BOI13_tracks)	Java	100 / 100	1267 ms	532808 KiB

tracks

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

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, count;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        grid = new int[H][W];

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

        br.close();

        pw.println(bfs());
        pw.flush();
    }

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

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

        while (!q.isEmpty()) {
            int[] curr = q.poll();

            N = Math.max(N, count[curr[0]][curr[1]]);

            for (int i = 0; i < 4; i++) {
                int nx = curr[0] + dx[i];
                int ny = curr[1] + 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[0]][curr[1]]) {
                    count[nx][ny] = count[curr[0]][curr[1]] + 1;
                    q.addLast(new int[]{nx, ny});
                } else {
                    count[nx][ny] = count[curr[0]][curr[1]];
                    q.addFirst(new int[]{nx, ny});
                }
            }
        }

        return N;
    }
}

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