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:

6 011113 333311 111113 331333 331111 333332 

Your program must then solve the maze. It will then output the correct path through the maze marked by 0s 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:

20 01113331111111311311 33311133313331113333 33333111313131333111 11113331333331131131 13133111313333111331 13113331111331133331 33133311331331333111 11133331331333333313 13133133331331311113 13111111111331331333 33133133331131111111 13131131133111333133 13333111313331113333 11113331111333133113 13313133313313111133 33111331311333133131 13331111311333333133 33131333331131111111 13331311133111333331 11133213111133311131 

Output:

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

3