For this homework you will be making a maze solver. Your program will take in fr

Question

For this homework you will be making a maze solver. Your program will take in from a file 2 things. The size of the square maze, and the maze itself. The maze will consists of numbers between 0 and 3, where 0 is the start of the maze, 1 is an open path, 3 is a wall, and 2 is the end of the maze. For example a 6x6 maze could be represented by the following file, there will be no spaces seperating the elements of the maze:

Your program must then solve the maze. It will then output the correct path through the maze marked by 0’s to the command line. For example for the maze above it may output the following solution(I added spaces to make it more readable not necessary):

000003 333301 110003 330333 330000 333330

You can assume that the input contains the exact amount of numbers needed and that it is a solvable maze, following the rules outlined above.

Save your program as a “Homework2.java” file. Your program should read from a file named “in.txt” if you have your program read from a different file you may recieve no credit for this assignment.

1

Your program does not need to find the shortest path, just a path from the start to the finish. For example on the following maze:

3 011 131 211

The following is an acceptable solution to the problem:

000 130 000

While the shortest path is actually the following:

011 031 011

You may also assume that the maze will be no larger than 40x40

1.1 Hints

• Recursion is your friend.
• Store the maze as a 2D array.
• Remember that arrays are pass by reference not value.

2 Extra Credit

For extra credit have your program find the shortest solution.

2

3 Another Maze

Input:

Output:

00003331111111311311 33300033313331113333 33333000313131333111 11113330333331131131 13133110313333111331 13113330000331133331 33133311330331333111 11133331330333333313 13133133330331311113 13111000000331331333 33133033331131111111 13131031133111333133 13333000313331113333 11113330001333133113 13313133303313111133 33111331300333133131 13331111310333333133 33131333330031111111 13331300033011333331 11133003000033311131

3

Explanation / Answer

import java.io.*; import java.util.*; import java.lang.*; import java.text.*; public class MazeSolve1 { public static void main(String[] args) { //Create arrayList of Points ArrayList MAZE = new ArrayList(); Scanner in = new Scanner(System.in); //Read File in System.out.print("Enter the file name: "); String fileName = in.nextLine(); fileName = fileName.trim(); FileReader reader = new FileReader(fileName+".txt"); Scanner in2 = new Scanner(reader); //Write file out FileWriter writer = new FileWriter("Numbers.out"); PrintWriter out = new PrintWriter(writer); boolean done = false; int maxCol = 0; int maxRow = 0; while(!done) { //creating array lists while (in2.hasNextLine()) { //Read next line String nextLine = in2.nextLine(); //Tokenize Line StringTokenizer st = new StringTokenizer(nextLine, " "); //Create temp ArrayList ArrayList temp = new ArrayList(); //While there are more tokens while (st.hasNextToken()) { String token = st.nextToken(); Points pt = new Points(); temp.add(pt); maxCol++ } MAZE.add(temp); maxRow++; } //create hold arraylist for max rows of maze -1 //create variables for start x and y coordinates ArrayList hold = new ArrayList(); hold = MAZE.get(maxRow - 1); int startColumn = hold.get(maxCol - 1); int startRow = hold.get(maxRow - 1); Point start = new Point(); start.setX(startColumn); start.setY(startRow); //initialize stack, and push the start position MyStack st = new ArrayStack(); st.push(start.toString1()); //south and east of start are edges of array start.setSouth(false); start.setEast(false); //while your position is not equal to point (0,0) [finish] while (st.peek() != "(0, 0)") { //getting the next coordinate to the North int nextY = start.getY() - 1; int nextX = start.getX(); //if character to the North is an O it's open and the North flag is true if (hold.get(nextY) = 'O' && start.getNorth() == true) { //set flags and push coordinate start.setNorth(false); st.push(start.toString1()); } //else pop from stack else { st.pop(); } //look at coordinate to the East nextX = start.getX() + 1; //if character to the East is a O and the East flag is true if (hold.get(nextX) = 'O' && start.getEast() == true) { //set flags and push coordinate start.setEast(false); st.push(start.toString1()); } //else pop from stack else { st.pop(); } //look at coordinate to the South nextY = start.getY() + 1; //if character to the South is a O and the West flag is true if (hold.get(nextY) = 'O' && start.getSouth() == true) { //set flags and push coordinate start.setSouth(false); st.push(start.toString1()); } //else pop from stack else { st.pop() } //keep looping until the top of the stack reads (0, 0) } done = true; } //Print the results System.out.println("---Path taken---"); for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.