import java.util.Scanner; /** * Calculates de minimun moves to get an open column (solution column) at the game "Open the way to the train" */ public class Solution { /** * Gets data from standard input */ private Scanner input = null; /** * A reference for the binary game matrix */ private int[][] obstacles = null; /** * A reference for the array that contains the total of necesary moves for every column to "open the way" */ private int[] costs = null; /** * The rows for the game matrix */ private int rows = 0; /** * The columns for the game matrix */ private int columns = 0; /** * Start the execution of the solution * @param args Command line arguments */ public static void main(String args[]) { Solution solution = new Solution(); solution.run(); } /** * Run the solution. This method is called from main() */ public void run() { // Create object to read data from standard input this.input = new Scanner(System.in); // The lowest amount of movements for every solution column int lowestCost = 0; // Get the rows and columns number from the standart input this.rows = input.nextInt(); this.columns = input.nextInt(); // Create a matrix with the given amount of rows and columns this.obstacles = new int[rows][columns]; // Create an array that contains the cost for every column this.costs = new int[columns]; // Get the matrix binary information from the standart input readMatrix(input); // If the game matrix is valid if(validateObstacles()) { // Get the amount of necessary moves for every column searchCosts(); // Calculate the lowest amount of moves (cost) lowestCost = obtainLowestCost(); // Print the lowest cost and every column that has this cost printSolutionColumns(lowestCost); } // Close the standard input this.input.close(); } /** * Gets de binary data from the standart input to fill the matrix */ public void readMatrix(Scanner input) { for(int row = 0; row < this.obstacles.length; row++) { for(int col = 0; col < this.obstacles[0].length; col++) { // Store a 0 or a 1 at the matrix direction this.obstacles[row][col] = input.nextInt(); } } } /** * Looks for a row in the matrix that does not have empty espaces to make a move * @return true if there is empty espaces for ever row * @return false if the matrix has at least one invalid row */ public boolean validateObstacles() { // The empty espaces for every row int emptyEspaces = 0; // A boolean to check if there is at least one invalid row boolean someInvalidRow = false; for(int row = 0; row < this.obstacles.length; row++) { // Restart the row empty espaces emptyEspaces = 0; for(int col = 0; col < this.obstacles[0].length; col++) { // If there is a 0 at the matrix direction, there is an empty espace at the row if(this.obstacles[row][col] == 0) // It is not necessary to accumulate the amount of empty espaces emptyEspaces = 1; } // If there is 0 empty espaces at the row if(emptyEspaces == 0) { // There is some invalid row at the matrix someInvalidRow = true; // Print a message to notify the invalid row an its number System.out.printf("Invalid row %d%n", row + 1); } } // If the method founds an invalid row return false, otherwise return true if(someInvalidRow) return false; else return true; } /** * Gets the cost for every column and store them in the costs array */ public void searchCosts() { // The cost of every column int cost = 0; for(int col = 0; col < this.obstacles[0].length; col++) { // Restart the cost count cost = 0; for(int row = 0; row < this.obstacles.length; row++) { // If there is a 1 at the matrix direction, it has to be moved if (this.obstacles[row][col] == 1) // Accumulate de total movements for the column cost cost += calculateMovements( obstacles[row], col); } // Assign the total cost for the column this.costs[col] = cost; } } /** * Calculates the lowest amount of moves for an element in a row * @return the integer of the lowest cost at the column index */ public int calculateMovements(int[] array, int index) { // The minimun cost for the element int movements = 0; // The cost by moving to the left and to the rigth, it would be 0 if there is no more 0 at the direction int leftMoves = 0; int rigthMoves = 0; // From the index to the left for(int place = index; place >= 0; place--) { // If there ir a 0, the left moves will be the diference between their index, // or maybe the diferece between the index an the 0 place if(array[place] == 0) { leftMoves = index - place; // Stop searching for more 0, it found the nearest to the left already break; } } // From the index to the rigth for(int place = index; place < array.length; place++) { // If there ir a 0, the rigth moves will be the diference between their index, // or maybe the diferece between the index an the 0 place if(array[place] == 0) { rigthMoves = place - index; // Stop searching for more 0, it found the nearest to the rigth already break; } } // Select the lower amount of moves movements = selectDirection(leftMoves, rigthMoves); return movements; } /** * Selects the lower cost by checking the left or rigth cost * @return the lower amount of moves between the the left and the rigth moves */ public int selectDirection(int left, int rigth) { // The lower amount of moves int moves = 0; // If a left or rigth move is 0, there is no 0 at that direction if(left == 0) moves = rigth; else if (rigth == 0) moves = left; // If the left an rigth moves are valid, it selects the lower if(left != 0 && rigth != 0) { if (left <= rigth) moves = left; else moves = rigth; } return moves; } /** * Checks the Costs array to get the lowest amount of movements in an determinate column * @return the integer of the lowest cost at the matrix */ public int obtainLowestCost() { // The lowest cost obtained, starting with the first cost int lowest = costs[0]; for(int index = 0; index < costs.length; index++) // If the cost at the index is lower than the actual, it becomes the lowest if(costs[index] <= lowest ) lowest = costs[index]; return lowest; } /** * Prints the the lowest amount of movements at the matrix and the columns that can afford it */ public void printSolutionColumns(int cost) { // Print the lowest cost System.out.printf("%d ",cost); // Check for any column that has the lowest cost and print them for(int index = 0; index < costs.length; index++) if(costs[index] == cost) System.out.printf("%d ", index + 1); } }