Submission #582483

#	Time	Username	Problem	Language	Result	Execution time	Memory
582483		coderInTraining	Tracks in the Snow (BOI13_tracks)	Java	0 / 100	147 ms	12424 KiB

tracks

import java.util.*;

class Main {
    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];

            if (cRow - 1 >= 0 && grid[cRow - 1][cColumn] != '.') {
                if (grid[cRow - 1][cColumn] == curChar) {
                    if (curDist < distances[cRow - 1][cColumn]) {
                        distances[cRow - 1][cColumn] = curDist;
                        Pair addingPair = new Pair (cRow - 1, cColumn);
                        queue.add(addingPair);
                    }
                }
                else {
                    if (curDist + 1 < distances[cRow - 1][cColumn]) {
                        distances[cRow - 1][cColumn] = curDist + 1;
                        Pair addingPair = new Pair (cRow - 1, cColumn);
                        queue.add(addingPair);
                    }
                }
            }

            if (cColumn + 1 < columns && grid[cRow][cColumn + 1] != '.') {
                if (grid[cRow][cColumn + 1] == curChar) {
                    if (curDist < distances[cRow][cColumn + 1]) {
                        distances[cRow][cColumn + 1] = curDist;
                        Pair addingPair = new Pair (cRow, cColumn + 1);
                        queue.add(addingPair);
                    }
                }
                else {
                    if (curDist + 1 < distances[cRow][cColumn + 1]) {
                        distances[cRow][cColumn + 1] = curDist + 1;
                        Pair addingPair = new Pair (cRow, cColumn + 1);
                        queue.add(addingPair);
                    }
                }
            }

            if (cRow + 1 < rows && grid[cRow + 1][cColumn] != '.') {
                if (grid[cRow + 1][cColumn] == curChar) {
                    if (curDist < distances[cRow + 1][cColumn]) {
                        distances[cRow + 1][cColumn] = curDist;
                        Pair addingPair = new Pair (cRow + 1, cColumn);
                        queue.add(addingPair);
                    }
                }
                else {
                    if (curDist + 1 < distances[cRow + 1][cColumn]) {
                        distances[cRow + 1][cColumn] = curDist + 1;
                        Pair addingPair = new Pair (cRow + 1, cColumn);
                        queue.add(addingPair);
                    }
                }
            }

            if (cColumn - 1 >= 0 && grid[cRow][cColumn - 1] != '.') {
                if (grid[cRow][cColumn - 1] == curChar) {
                    if (curDist < distances[cRow][cColumn - 1]) {
                        distances[cRow][cColumn - 1] = curDist;
                        Pair addingPair = new Pair (cRow, cColumn - 1);
                        queue.add(addingPair);
                    }
                }
                else {
                    if (curDist + 1 < distances[cRow][cColumn - 1]) {
                        distances[cRow][cColumn - 1] = curDist + 1;
                        Pair addingPair = new Pair (cRow, cColumn - 1);
                        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