import java.util.*;public class Assignment2 { byte[][] maze; byte[] 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"); //System.out.println(tmpMaze.length() + "\n"); maze = new byte[numLines][numColumns]; mousePos = new byte[2]; cheesePos = new byte[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++) { //System.out.print(tmpMaze.charAt(i*(1+numColumns) + j) + "i: " + i + " j: " + 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] = (byte)i; mousePos[1] = (byte)j; // store position for later numMouse++; break; case 'C': maze[i][j] = 'C'; cheesePos[0] = (byte)i; cheesePos[1] = (byte)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; } } //System.out.println("New line!!"); } if(numMouse != 1 || numCheese != 1) { System.out.println("There has to be one mouse and one cheese!"); return false; } //System.out.println("\n\n" + tmpMaze); System.out.println("The maze from array: "); for(int i = 0; i < numLines; i++) { for(int j = 0; j < numColumns; j++) System.out.print((char)maze[i][j]); System.out.println(""); } return true; } public void createPath() { // works with blocks of 3x3 chars, mouse in the middle int pathLength = 0, pathLengthSave = 0; // how long the current path is int openingsInThisBlock = -1; // how many openings in every 3x3 block we have byte[] currPos = mousePos.clone(); // start at mouse position byte[] startNextTime; byte[][] tmpMaze = maze.clone(); // this is what we work with boolean foundTheCheese = false; LinkedList<byte[]> savedPos = new LinkedList<byte[]>(); LinkedList<Integer> savedLength = new LinkedList<Integer>(); LinkedList<Integer> foundTheCheeseLength = new LinkedList<Integer>(); LinkedList<byte[][]> pathToCheese = new LinkedList<byte[][]>(); // save the path to the cheese :D byte[][] nextPos = new byte[4][2]; // 4 different paths are possible, 2 coordinates for every path System.out.println("currpos: " + currPos[0] + " " + currPos[1]); do { openingsInThisBlock = -1; // reset this if(!savedLength.isEmpty()) pathLength = (savedLength.poll()).intValue(); // preset length if(!savedPos.isEmpty()) currPos = savedPos.poll(); // preset position byte[][] newMaze = maze.clone(); // copy a new maze to create a path in while(openingsInThisBlock != 0 && !foundTheCheese) { // we still have somewhere to go! openingsInThisBlock = 0; for(int i = 0; i < 3; i++) { // loop through 3 positions at a time to find openings 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)] == ' ') { // we have a open path, lets walk it! System.out.println("Found a path! Saving it for later"); nextPos[openingsInThisBlock][0] = (byte)(currPos[0] + i - 1); // save y-coordinate nextPos[openingsInThisBlock][1] = (byte)(currPos[1] + j - 1); // save x-coordinate openingsInThisBlock++; // we found a opening here } // we found the cheese!! walk straight to it and quit the app else if(tmpMaze[(currPos[0] + i - 1)][(currPos[1] + j - 1)] == 'C') { System.out.println("We found the cheese!! We're done here! " + i + " " + j); openingsInThisBlock = 0; tmpMaze[currPos[0]][currPos[1]] = '.'; // mark where we have already walked currPos[0] += (i - 1); currPos[1] += (j - 1); // move mouse to new pos pathLength++; // length is increased foundTheCheese = true; openingsInThisBlock = 0; // don't do anything stupid! pathToCheese.add(newMaze); } } } if(openingsInThisBlock == 1) { System.out.println("Walked a path!"); tmpMaze[currPos[0]][currPos[1]] = '.'; // mark our previous position newMaze[currPos[0]][currPos[1]] = '.'; // write pos in a fresh maze currPos[0] = nextPos[0][0]; // move mouse to new pos currPos[1] = nextPos[0][1]; tmpMaze[currPos[0]][currPos[1]] = 'M'; // mark where the mouse is atm pathLength++; // length is increased } else if(openingsInThisBlock == 2) { System.out.println("We have "+ openingsInThisBlock + " paths, save this position and walk the first"); savedLength.add(new Integer(pathLength)); // save length too savedPos.add(currPos.clone()); // position saved for next turn tmpMaze[currPos[0]][currPos[1]] = '.'; // mark our previous position newMaze[currPos[0]][currPos[1]] = '.'; // write pos in a fresh maze currPos[0] = nextPos[0][0]; // move mouse to new pos currPos[1] = nextPos[0][1]; tmpMaze[currPos[0]][currPos[1]] = 'M'; // mark where the mouse is atm pathLength++; // length is increased } } // Print shit System.out.println("Length of path: " + pathLength + ". The solved maze from array: "); 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(""); } } while(!savedPos.isEmpty()); if(!pathToCheese.isEmpty()) { System.out.println("Length of path: " + pathLength + ". ACTUAL PATH TO CHEESE: "); byte[][] fineMaze = pathToCheese.poll(); for(int k = 0; k < fineMaze.length; k++) { for(int q = 0; q < fineMaze[k].length; q++) System.out.print((char)fineMaze[k][q]); System.out.println(""); } } /*if(foundTheCheese) { } System.out.println("Length of path: " + pathLength + ". The solved maze from array: "); for(int k = 0; k < tmpMaze.length; k++) { for(int q = 0; q < tmpMaze[i].length; q++) System.out.print((char)tmpMaze[k][q]); System.out.println(""); } */ /*for(int i = 1; i < (maze.length-1); i++) for(int j = 1; j < (maze[i].length-1); j++) { for(int k = 0; k < ) }*/ } /** * @param args the command line arguments */ public static void main(String[] args) { Assignment2 app = new Assignment2(); if(!app.readInput()) { // couldn't create maze System.out.println("Quitting"); return; } app.createPath(); }}