import java.util.Scanner; import java.lang.Math; /** * Replace this JavaDoc comment for the purpose of this class */ public class Solution { /** * Gets data from standard input */ private Scanner input = 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); //Variables with the matrix size int matrixRows = input.nextInt(); int matrixCols = input.nextInt(); //Matrix street, contain the given matrix(street) int [][] street = new int [matrixRows][matrixCols]; //Array with the minimum quantity of movements required per col int[] energyRequired = new int [matrixCols]; read(input ,street, matrixRows, matrixCols); if (checkForInvalid(street, matrixRows, matrixCols)){ //Do nothing, the row is invalid } else{ for (int currentCol = 0;currentCol < matrixCols; ++currentCol){ energyRequired[currentCol] = getWastedEnergy(street, currentCol, matrixRows, matrixCols); } minMovesRequired(energyRequired, matrixCols); } // Close the standard input this.input.close(); } /** *Introduces all values in the matrix street */ public void read(Scanner input,int [][]street, int matrixRows, int matrixCols){ // Read all values for the matrix for ( int row = 0; row < matrixRows; ++row ) { // Read all values for current row for ( int col = 0; col < matrixCols; ++col ) { street[row][col] = input.nextInt(); } } } /** * search if all rows haave a single cero, otherwise it will print "invalid row, and its location" * checkForInvalid = true, means the matrix has a invalid row * checkForInvalid = false, means not invalid rows founded */ public boolean checkForInvalid(int [][]street, int matrixRows, int matrixCols){ int counter = 0; int totalCount = 0; //check if boolean validStreet = false; // Read all values for the matrix for ( int row = 0; row < matrixRows; ++row ) { // Read all values for current row for ( int col = 0; col < matrixCols; ++col ) { //inputs can also be introduced here //street[row][col] = input.nextInt(); if(street[row][col] == 1 ){ //Count the number of 1's in a row, to later compare counter++; } } //Compare the amount of 1's founded with the total rows length //if the amount its the same, means there are only 1's in the row, an it is invalid. Otherwise it have a possible solution if (counter == matrixCols){ // Print all the invalid rows the have been founded System.out.println("Invalid row "+ (row + 1)); validStreet = true; } //Count from cero to start again the counts of ceros in the row counter =0; } return validStreet; } /** * look for evey "1"() in each col in the matrix */ public int getWastedEnergy(int [][]street, int currentCol, int matrixRows, int matrixCols){ //Accumulates all the movements required per col int wastedEnergy = 0; //search in every col for a "1"(obstacle) for ( int row = 0; row < matrixRows; ++row ){ if (street[row][currentCol] == 1){ // Accumulates all the quantity of required movements per col wastedEnergy += getClosestCero(street, row, currentCol, matrixCols); } } return wastedEnergy; } /** * search for every "0" in the current row, where the "1" has been found */ public int getClosestCero(int [][]street, int row,int currentCol, int matrixCols){ int requiredMoves = 0; int latest = matrixCols; for ( int col = 0; col < matrixCols; ++col ){ if (street[row][col] == 0){ requiredMoves = closestMove(street,col, currentCol); if (requiredMoves < latest){ latest = requiredMoves; } } } return latest; } /** * Calculates the total of steps required to clear the path * */ public int closestMove(int [][]street, int col,int currentCol){ int closest = Math.abs(col - currentCol); return closest; } /** * Find in the array energyRequired the less quantity of moves required */ public void minMovesRequired(int[]energyRequired, int matrixCols){ //Introduces the biggest possible int number so that we would always have the smallest possible number in the array. int minMoves = 2147483647; //Read all the array with the movements quantity for (int index = 0;index <( matrixCols); ++index){ //Comparisson to get the smallest number if(energyRequired[index] < minMoves){ minMoves = energyRequired[index]; } } //print the smallest quantity of movements required System.out.print(minMoves); printRoads(minMoves, energyRequired, matrixCols); } /** * Uses the less quantity of moves required and searches for all roads with the same required moves */ public void printRoads(int minMoves, int[]energyRequired, int matrixCols){ //Search in the array energyRequired for the col number with the same required movements for (int index = 0;index < matrixCols; ++index){ //Search all the cols(paths) that have the same ammount of required movements if (energyRequired[index] == minMoves) System.out.print(" "+(index + 1) ); } } }