import java.util.Scanner; /** * Finds the most optymal column for the train rail to pass on the game Matrix. */ public class Solution { /** * Gets data from standard input */ private Scanner input = null; /** * This will be the matrix used for the game. */ private int matrix [][] = null; /** * The array that stores the movements needed by column. */ private int movements[] = 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); // Reads the row and column values needed int rows = input.nextInt(); int cols = input.nextInt(); // Create object for the matrix to be used this.matrix = new int[rows][cols]; // Create object for the movements to be stored this.movements = new int [cols]; readMatrix(); // Checks the validness of the matrix and prints error if it isn't. if(matrixIsValid()) { calculateSolution(); printSolution(); } // Close the standard input this.input.close(); } /** * Fills the matrix from input */ public void readMatrix() { for (int row = 0; row < this.matrix.length; ++row) { for (int col = 0 ; col < this.matrix[row].length; ++col) { this.matrix[row][col] = input.nextInt(); } } } /** * Checks if the matrix is valid, containing at least one zero on each row. * If it isn't valid, prints the error message. * @Return A boolean indicating if the matrix is valid. */ public boolean matrixIsValid() { boolean isValid = true; int whiteSpaces [] = new int [this.matrix.length]; // Counts the amount of zeros on each row for (int row = 0; row < this.matrix.length; ++row) { for (int col = 0 ; col < this.matrix[row].length; ++col) { if (matrix[row][col] == 0) { whiteSpaces[row] ++ ; } } } // Finds if there's a row with no zeros for (int count = 0; count < whiteSpaces.length; ++count) { if(whiteSpaces[count] == 0) isValid = false; } if (! isValid) printError(whiteSpaces); return isValid; } /** * Prints the rows that have no zeros as errors */ public void printError(int[] whiteSpaces) { // Prints all the rows with no zeros. for (int count = 0; count < whiteSpaces.length; ++count) { if(whiteSpaces[count] == 0) System.out.printf("Invalid row %d%n",count + 1); } } /** * Fills the movements array with the movements neeeded to clear the way on each column */ public void calculateSolution() { for (int col = 0; col< movements.length; ++ col) { getMovements(col); } } /** * Calculates the movements needed to clear a specific column. * @Param the column to be checked. */ public void getMovements(int col) { for (int row = 0; row < this.matrix.length; ++row) { // Calculates movements needed by the left int left = 0; int cell = col; while( cell >= 0 && matrix[row][cell] !=0 ) { left ++; -- cell; } // Calculates movements needed by the right int right = 0; cell = col; while(cell < matrix[row].length && matrix [row][cell] != 0) { right ++; cell ++; } //Avoids adding a side that has no white spaces if ( left == col+1) this.movements[col] += right; else if (right == movements.length - col) this.movements[col]+= left; // Adds the most optymal side else this.movements[col] += right > left ? left : right; } } /** * Prints all the columns where the least amount of movements are needed */ public void printSolution() { int bestCol = 0; // Finds the column with the least amount of movements needed. for (int count = 0; count < movements.length; ++ count) { if ( movements[count] < movements[bestCol]) { bestCol = count; } } System.out.print(movements[bestCol]); // Prints all the columns with this amount of movements for (int count = 0; count < movements.length; ++ count) { if ( movements[count] == movements[bestCol]) { System.out.printf(" %d", count +1); } } } }