import java.util.Scanner; /** * Solution for test 2 */ public class Solution { /** * Gets data from standard input */ private Scanner input = null; /** * The matrix that has to be fixed so the train can pass */ private String[][] level = null; /** * The array that will save the solutions for each column */ private int[] results = null; /** * 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); // Read rows and columns int rows = input.nextInt(); int cols = input.nextInt(); // Create the matrix and array with the specified data level = new String[rows][cols]; results = new int[cols]; input.nextLine(); input.nextLine(); // If we read the matrix correctly, get the solutions and print them if(readLevel(rows, cols)) { getSolutions(rows, cols); printBestSolutions(cols); } // Close the standard input this.input.close(); } /** * Reads the level from standard input * @param rows the total rows of the matrix * @param cols the total columns of the matrix * @return true if the method read the matrix succesfully */ public boolean readLevel(int rows, int cols) { boolean valid = true; // Create two variables to store the amount of 1's and 0's in a row int zeroes = 0; int ones = 0; // Read the matrix from standard input for (int row = 0; row < rows; ++row) { zeroes = 0; ones = 0; for (int col = 0; col < cols ; ++col) { String space = input.next().trim(); if (space.equals("1")) ++ones; else if (space.equals("0")) ++zeroes; level[row][col] = space; } // After reading the row, validate if it has at least one 0 if (!validRow(zeroes)) { System.out.println("Invalid row " + (row + 1)); valid = false; } // if we reach an end of line, change the line if(row < rows -1) input.nextLine(); } return valid; } /** * Validates if a row has at least one 0 * @param zeroes the total 0's * @return true if there is at least one 0 */ public boolean validRow(int zeroes) { return zeroes > 0; } /** * Gets all the solutions of the actual level * @param rows the total rows of the matrix * @param cols the total columns of the matrix */ public void getSolutions(int rows, int cols) { for (int col = 0; col < cols; ++col) { for (int row = 0; row < rows; ++row) { moveCars(col, cols, row, rows); } } } /** * Move the cars to the left or right to make the position empty * @param col the actual column it is positioned * @param cols the total columns of the matrix * @param row the actual row it is positioned * @param rows the total rows of the matrix */ public void moveCars(int col, int cols, int row, int rows) { int leftMoves = 0; int rightMoves = 0; // If we are positioned on the most-to-the-left column, move right only if (col - 1 == -1) { rightMoves = moveRight(col, row, cols); results[col] += rightMoves; } // Otherwise, if we are positioned on the most-to-the-right column, move left only else if (col + 1 == cols) { leftMoves = moveLeft(col, row, cols); results[col] += leftMoves; } // Otherwise, we are between the limits of the matrix else { // Move both sides leftMoves = moveLeft(col, row, cols); rightMoves = moveRight(col, row, cols); // Check which movements are the smallest and add them if (rightMoves < leftMoves) results[col] += rightMoves; else results[col] += leftMoves; } } /** * Gets the moves to the left needed to clear the position * @param col the actual column * @param row the actual row * @param cols the total columns * @return the moves to the left needed to clear the position */ public int moveLeft(int col, int row, int cols) { int moves = 0; // Move to the left until a 0 is found for (int position = col; position >= 0; --position) { // If we are in the last position and it is a 1, there's no solution in this side if (position == 0 && level[row][position].equals("1")) { return 999999; } // While a 1 is found, add one move to the left if (level[row][position].equals("1")) { ++moves; } // When the 0 is found, break the loop and return the moves needed else if (level[row][position].equals("0")) { break; } } return moves; } /** * Gets the moves to the right needed to clear the position * @param col the actual column * @param row the actual row * @param cols the total columns * @return the moves to the right needed to clear the position */ public int moveRight(int col, int row, int cols) { int moves = 0; // Move to the right until a 0 is found for (int position = col; position < cols; ++position) { // If we are in the last position and it is a 1, there's no solution in this side if (position == cols - 1 && level[row][position].equals("1")) { return 999999; } // While a 1 is found, add one move to the right if (level[row][position].equals("1")) { ++moves; } // When the 0 is found, break the loop and return the moves needed else if (level[row][position].equals("0")) { break; } } return moves; } /** * Prints the best solutions that a level has * @param cols the maximum cols of the matrix */ public void printBestSolutions(int cols) { // Start assuming the best result is in the left int minMoves = results[0]; // Check if there are better solutions for(int index = 1; index < cols; ++index) { if (results[index] < minMoves) { minMoves = results[index]; } } // Print the minimum moves found System.out.print(minMoves + " "); // Print the columns that have the same moves for (int index = 0; index < cols; ++index) { if (minMoves == results[index]) { System.out.print(index+1 + " "); } } } }