import java.io.PrintStream; import java.util.Scanner; import java.util.regex.Pattern; /** * Marks the solution path within a maze with breadcrumbs */ public class Solution { /** * Gets data from standard input */ private Scanner input = null; /** * The maze to be solved is a matrix of chars * where '|' stands for a wall, ' ' a passage, * 'A' the entrance (start), and 'B' the exit (end) */ private Maze maze = 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); int rows = this.input.nextInt(); int columns = this.input.nextInt(); // Discard two new line chars this.input.nextLine(); this.input.nextLine(); this.maze = new Maze(rows, columns); this.maze.read( this.input ); if ( this.maze.findPath() ) { this.maze.print(); } else { System.out.println("No solution path"); } // Close the standard input this.input.close(); } } /*public*/ class Maze { private char[][] map = null; private int startingRow = -1; private int startingColumn = -1; // Constructor: method in charge of initializing the attributes // when an object is created public Maze(int rows, int columns) { if ( rows > 0 && columns > 0 ) { this.map = new char[rows][columns]; } } /** * ya no (This method assumes the input has nothing as the delimiter) */ public void read(Scanner input) { Pattern oldDelimiter = input.delimiter(); input.useDelimiter(""); for ( int row = 0; row < this.map.length; ++row ) { for ( int column = 0; column < this.map[row].length; ++column ) { this.map[row][column] = input.next().charAt(0); if ( this.map[row][column] == 'A' ) { this.startingRow = row; this.startingColumn = column; } } if ( input.hasNextLine() ) { input.nextLine(); } } input.useDelimiter(oldDelimiter); } public boolean findPath() { if ( this.startingRow >= 0 && this.startingColumn >= 0 ) { return this.findPathFrom(this.startingRow, this.startingColumn); } else { return false; } } private boolean findPathFrom(int row, int column) { if ( row >= 0 && row < this.getRows() && column >= 0 && column < this.getColumns() ) { switch ( this.map[row][column] ) { case 'B': return true; case '|': return false; case 'A': case ' ': this.map[row][column] = '.'; // North if ( this.findPathFrom(row - 1, column) == true ) { return true; } // East if ( this.findPathFrom(row, column + 1) == true ) { return true; } // South if ( this.findPathFrom(row + 1, column) == true ) { return true; } // West if ( this.findPathFrom(row, column - 1) == true ) { return true; } this.map[row][column] = ' '; return false; default: return false; } } else { return false; } } public int getRows() { /* if ( this.map == null ) return 0; else return this.map.length; */ return this.map != null ? this.map.length : 0; } public int getColumns() { return this.map != null ? this.map[0].length : 0; } public void print() { this.map[this.startingRow][this.startingColumn] = 'A'; for ( int row = 0; row < this.map.length; ++row ) { for ( int column = 0; column < this.map[row].length; ++column ) { System.out.print( this.map[row][column] ); } System.out.println(); } } }