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 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:

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