/** * * @author inoxor */ import java.util.*; public class Assignment2 { byte[][] maze; short[] mousePos, cheesePos; // {i, j} from maze /** Creates a new instance of Assignment2 */ public Assignment2() { } /** Reads input from user and puts the result in a byte-array */ public boolean readInput() { Scanner scan = new Scanner(System.in); String line = "", tmpMaze = ""; int numLines = 0, numColumns = -1, numMouse = 0, numCheese = 0; System.out.println("Enter the maze:"); while(true) { line = scan.nextLine(); if(numColumns == -1) numColumns = line.length(); // set the length of the first row if(line.equals("END")) // we're done break; numLines++; if(numColumns != -1 && numColumns != line.length()) { // all lines must have same length System.out.println("Faulty maze! All lines must have the same length"); System.out.print(tmpMaze); return false; } tmpMaze += line + "\n"; } System.out.println("numLines: " + numLines + " numColumns: " + numColumns + "\n"); maze = new byte[numLines][numColumns]; mousePos = new short[2]; cheesePos = new short[2]; for(int i = 0; i < numLines; i++) { // here we put the result in a byte-array for(int j = 0; j < numColumns && tmpMaze.charAt(i*(1+numColumns) + j) != '\n'; j++) { switch(tmpMaze.charAt(i*(1+numColumns) + j)) { case 'x': maze[i][j] = 'x'; break; case ' ': maze[i][j] = ' '; break; case 'M': maze[i][j] = 'M'; mousePos[0] = (short)i; mousePos[1] = (short)j; // store position for later numMouse++; break; case 'C': maze[i][j] = 'C'; cheesePos[0] = (short)i; cheesePos[1] = (short)j; // store position for later numCheese++; break; default: System.out.println("Other char than the allowed ones found at " + i + " " + j + ": " + tmpMaze.charAt(i*(1+numColumns) + j)); return false; } } } if(numMouse != 1 || numCheese != 1) { System.out.println("There has to be one mouse and one cheese!"); return false; } return true; } /** This one floods the maze and then stops when it finds the cheese and does a * backtrace. It works with 3x3 blocks to find new openings, and then adds them to a list which then * gets checked in the right order. Every dot saves the position of the dot that filled it, that way * it is easy to backtrace. */ public void createPath2() { short[][][] whoFilledMe = new short[maze.length][maze[0].length][2]; // 3d array LOOOOL LinkedList floodPos = new LinkedList(); // these are essentially all mouse-positions short[] currPos = new short[2]; // this is what we work with short[] tmpPos = new short[2]; byte[][] tmpMaze = new byte[maze.length][maze[0].length]; // = maze.clone(); // this is what we work with byte[][] backtraceMaze = new byte[maze.length][maze[0].length];; // = maze.clone(); // this is what we use to generate nice picture when path is found int numberBacktraced = 0; boolean foundTheCheese = false; for(int i = 0; i < maze.length; i++) { // we have to do deepcopy for two-dimension array tmpMaze[i] = maze[i].clone(); backtraceMaze[i] = maze[i].clone(); } floodPos.add(mousePos.clone()); // we start with mouseposition while(!foundTheCheese) { if(!floodPos.isEmpty()) currPos = floodPos.poll(); // grab the position we're gonna work with! else { System.out.println("WHAT NO POSITIONS TO WORK WITH??"); break; } for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { if((i == 0 && j == 0) || (i == 2 && j == 0) || (i == 0 && j == 2) || (i == 2 && j == 2) || foundTheCheese) continue; // we don't want to check corners. we don't want to do more if we found cheese if(tmpMaze[(currPos[0] + i - 1)][(currPos[1] + j - 1)] == 'C') { // found the cheese System.out.println("!!!!!!!!Found the cheeze!!!!!!!"); foundTheCheese = true; tmpPos = currPos.clone(); // lets start at the coordinates before the cheese while(!(tmpPos[0] == mousePos[0] && tmpPos[1] == mousePos[1])) { // then we're done backtraceMaze[tmpPos[0]][tmpPos[1]] = '.'; // mark our path if(tmpPos[0] == 0 || tmpPos[1] == 0) { System.out.println("Got path 0 in backtrace, something's not good"); break; } // now move backwards 1 step short[] tmpTmp = new short[2]; // so things don't fuck up down here tmpTmp[0] = whoFilledMe[ tmpPos[0] ][ tmpPos[1] ][0]; tmpTmp[1] = whoFilledMe[ tmpPos[0] ][ tmpPos[1] ][1]; tmpPos = tmpTmp.clone(); numberBacktraced++; } continue; // do not do stupid shit afterwards } if(tmpMaze[(currPos[0] + i - 1)][(currPos[1] + j - 1)] == ' ') { // we have a open path, lets save it tmpMaze[currPos[0]][currPos[1]] = '.'; // mark where we have already walked tmpPos[0] = (short)(currPos[0] + i - 1); // save y-coordinate tmpPos[1] = (short)(currPos[1] + j - 1); // save x-coordinate tmpMaze[tmpPos[0]][tmpPos[1]] = '.'; if( whoFilledMe[tmpPos[0]][tmpPos[1]][0] == 0 && whoFilledMe[tmpPos[0]][tmpPos[1]][1] == 0) { whoFilledMe[tmpPos[0]][tmpPos[1]][0] = currPos[0]; whoFilledMe[tmpPos[0]][tmpPos[1]][1] = currPos[1]; } floodPos.add(tmpPos.clone()); // we save this walkable path } } } } for(int k = 0; k < tmpMaze.length; k++) { for(int q = 0; q < tmpMaze[k].length; q++) System.out.print((char)tmpMaze[k][q]); System.out.println(); } if(foundTheCheese) { System.out.println("\nPath is " + numberBacktraced + " units long. Here is the solution:"); for(int k = 0; k < backtraceMaze.length; k++) { for(int q = 0; q < backtraceMaze[k].length; q++) System.out.print((char)backtraceMaze[k][q]); System.out.println(); } } else { System.out.println("We didn't find the cheese :("); } } public static void main(String[] args) { Assignment2 app = new Assignment2(); if(!app.readInput()) { // couldn't create maze System.out.println("Quitting"); return; } long timeBegin = System.nanoTime(); app.createPath2(); long estimatedTime = System.nanoTime() - timeBegin; System.out.println("Execution took " + estimatedTime/1000000 + " ms."); } }