import java.util.Scanner; /** * This class solves the problem * of the train game, in order to get * the most effective way to open a way * for the train */ public class TrainGameSolution { /** * 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[]) { TrainGameSolution TrainGameSolution = new TrainGameSolution(); TrainGameSolution.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 size of the rows and the columns int rows = input.nextInt(); int cols = input.nextInt(); // Ignores the white line in the input input.nextLine(); // Generates an instance of gameChecker, and the constructor needs the rows and cols GameChecker gameChecker = new GameChecker(rows,cols); // Reads the data of the matrix given by the user gameChecker.readLevel(input); // If the game isValid if (gameChecker.isValid()) { // Check the amount of energy neccesary for each column gameChecker.checkGameStatus(); gameChecker.printResults(); } } } /** * This is the model class thats make all the * comprobations and the algorithmical part * in order to the generate the best roads * for the train * */ class GameChecker { // The matrix that is gonna be worked private int gameMatrix[][] = null; // A flag in order to know if a row is valid private boolean isValid = false; // A copy of the number of rows private int rows = 0; // A copy of the number of columns private int cols = 0; // A vector with the results for each column private int results[] = null; /** * This constructor in the one in charge * of filling all the class atributes, even creates * the matrix with its respective dimension */ public GameChecker(int rows, int cols) { results = new int[cols]; gameMatrix = new int[rows][cols]; this.rows = rows; this.cols = cols; } /** * This method reads all the "cars" data * represented by ones or zeros, and fills * the matrix with it */ public void readLevel(Scanner input) { // This external "for" go through the rows for (int rowsIndex = 0; rowsIndex < rows; rowsIndex++) { // Every new row the value isValid returns to false isValid = false; // This go through the columns for (int colsIndex = 0; colsIndex < cols; colsIndex++) { // The next int in the input, its saved in that space of the matrix gameMatrix[rowsIndex][colsIndex] = input.nextInt(); // If there is at leats a 0 in that row if (gameMatrix[rowsIndex][colsIndex] == 0) { // The row is valid isValid = true; } } // If is Invalid after all checks then, print that the row is invalid if (isValid == false) { System.out.println("Invalid row " + (rowsIndex + 1) ); } } } /** * This method goes through the columns calling the method * that checks the necessary * amount of energy for each space, and the added to it respective * column family */ public void checkGameStatus() { // Goes trough all the columns for (int colsIndex = 0; colsIndex < cols ; ++colsIndex) { // Goes through that column's rows for (int rowsIndex = 0; rowsIndex < rows ; ++rowsIndex) { // Save in the vector results, of that column the amount of energy necessary results[colsIndex] += checkNecessaryEnergy(rowsIndex, colsIndex); } } } /** * Makes the necessary comprobations for each box * and according to the movements determinates the necessary * energy * @ return the total energy for that box */ private int checkNecessaryEnergy(int rowsIndex, int colsIndex) { // If the number is 0, that means you dont need to move if(gameMatrix[rowsIndex][colsIndex] == 0) { return 0; } // If the element before is 0, then you have to move one space else if(colsIndex > 0 && gameMatrix[rowsIndex][colsIndex - 1] == 0 ) { return 1; } // If the element after is 0, you have to move one space else if (colsIndex != cols - 1 && gameMatrix[rowsIndex][colsIndex + 1 ] == 0 ) { return 1; } // You have to move n spaces, to your left or your right else { return findClosestZero(rowsIndex, colsIndex); } } /** * In the case it have to move n space to the left of the * right, it check the amount of movement of every side * and the it evaluates which one is the correct, and the * closes way for doing it * @ return the total moves */ public int findClosestZero(int rowsIndex,int colsIndex) { // Variables that storage save the total of moves of each side int rightZeroMoves = findClosestRightZero(rowsIndex, colsIndex); int leftZeroMoves = findClosestLeftZero(rowsIndex, colsIndex); // If rightMoves is higher that the leftMoves if (rightZeroMoves > leftZeroMoves && leftZeroMoves != 0) { // Left moves is the best way return leftZeroMoves; } // If the value isnt zero, and the number of moves doesnt isnt is the limit of the matrix else if (rightZeroMoves != 0 && colsIndex + rightZeroMoves < cols) { return rightZeroMoves; } // The program assumes, that leftMoves is the best else { return leftZeroMoves; } } /** * This method gets the coordinates of the element * that its been analyzed and goes backwards until * it finds a zero, or there is nothing more to check * and have a counter that determinates the amount of time * that the process repeats * @ return the total of energy waster */ private int findClosestLeftZero(int rowsIndex, int colsIndex) { // The variable that stores the total of energy necessary int energy = 0; // While the array dont go out of bounds, and dont find a 0 while (colsIndex > 0 && gameMatrix[rowsIndex][colsIndex] != 0 ) { // Add to the total amount of energy one energy++; // Go one position behind colsIndex--; } // If the last number checked is a one, that means there are no 0s if (gameMatrix[rowsIndex][colsIndex] == 1 ) { return 0; } else { // returns the accumulator return energy; } } /** * This method gets the coordinates of the element * that its been analyzed and goes forward until * it finds a zero, or there is nothing more to check * and have a counter that determinates the amount of time * that the process repeats * @ return the total of energy waster */ private int findClosestRightZero(int rowsIndex, int colsIndex) { // The variable that stores the total of energy necessary int energy = 0; // While the array dont go out of bounds, and dont find a 0 while (colsIndex != cols && gameMatrix[rowsIndex][colsIndex] != 0 ) { // Add to the total amount of energy one energy++; // Go one position forward colsIndex++; } // If the last number checked is a one, that means there are no 0s if ( energy == 1 && colsIndex <= cols ) { return 0; } else { // returns the total amount of energy return energy; } } /** * This method print the final results, that means that it * prints all the columns with the the min amount of * energy * */ public void printResults() { // A variable to store the minimun value int min = results[0]; // Goes thorugh all the results vector for (int counter = 0; counter < results.length; counter++) { // If the element in that position is less than the minimun, that means that value is the new minimun if (results[counter] < min) { min = results[counter] ; } } // Prints the amount of min energy System.out.printf("%d ", min ); // Goes checking all positions of the values equals to minimum and print them for (int index = 0; index < results.length; index++) { if (results[index] == min) { System.out.printf("%d ", index + 1); } } } /** * Getter for the isValid property of the class */ public boolean isValid() { return this.isValid; } }