Submission #582484

#	Time	Username	Problem	Language	Result	Execution time	Memory
582484		coderInTraining	Tracks in the Snow (BOI13_tracks)	Java	0 / 100	162 ms	12356 KiB

tracks

import java.util.*;

class Main {

    public static int [] dR = {-1, 0, 1, 0};
    public static int [] dC = {0, 1, 0, -1};
    public static void main (String[]args) {
        Scanner scan = new Scanner (System.in);

        int rows = scan.nextInt();
        int columns = scan.nextInt();

        char [][] grid = new char [rows][columns];

        for (int i = 0; i < rows; i++) {
            String line = scan.next();

            for (int j = 0; j < columns; j++) {
                grid[i][j] = line.charAt(j);
            }
        }

        int [][] distances = new int [rows][columns];

        for (int i = 0; i < rows; i++)  {
            Arrays.fill(distances[i], Integer.MAX_VALUE);
        }

        distances[0][0] = 1;

        Queue <Pair> queue = new LinkedList <Pair>();
        Pair startingPair = new Pair (0, 0);
        queue.add(startingPair);

        while (queue.isEmpty() == false) {
            Pair curPair = queue.poll();
            int cRow = curPair.row;
            int cColumn = curPair.column;
            int curDist = distances[cRow][cColumn];

            char curChar = grid[cRow][cColumn];

            for (int i = 0; i < 4; i++) {
                int nextRow = cRow + dR[i];
                int nextColumn = cColumn + dC[i];

                if (nextRow >= rows || nextColumn >= columns || nextRow < 0 || nextColumn < 0) {
                    continue;
                }

                if (grid[nextRow][nextColumn] == '.') {
                    continue;
                }

                if (grid[nextRow][nextColumn] == curChar) {
                    if (curDist < distances[nextRow][nextColumn]) {
                        distances[nextRow][nextColumn] = curDist;
                        Pair addingPair = new Pair (nextRow, nextColumn);
                        queue.add(addingPair);
                    }
                }
                else {
                    if (curDist + 1 < distances[nextRow][nextColumn]) {
                        distances[nextRow][nextColumn] = curDist + 1;
                        Pair addingPair = new Pair (nextRow, nextColumn);
                        queue.add(addingPair);
                    }
                }
            }
        }

        int maxDist = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {

                if (grid[i][j] == '.') {
                    continue;
                }

                maxDist = Math.max(maxDist, distances[i][j]);
            }
        }

        System.out.println(maxDist);
    }

    private static class Pair {
        int row;
        int column;

        public Pair (int row, int column) {
            this.row = row;
            this.column = column;
        }
    }
}

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