CS12, Extra Credit

Assigned: November 23 ^rd, 2001

Due: December 3^rd, 2001, 10pm

Topic

Recursive traversal of a maze.

A maze can be represented on a computer in a two dimensional array of 1s and 0s, where a 0 represents a blocked path, and a 1 means you can walk through. If the maze is represented in an n x m array MAZE[n ][m], the entrance is at MAZE[0][0], and the exit is at MAZE[n -1][m-1].

From each position in the maze, you can potentially travel in four directions -- north, east, south and west. Of course, if there is a 0 in the direction you want to travel, then you cannot go in that way.

If your position in the maze is row i column j, you can try to travel to each of the following four positions:

direction	row	column
north	i - 1	j
east	i	j+1
south	i + 1	j
west	i	j-1

With each new location, examine the four possible moves in order. If the new location is a valid one (value in the array is 1), then try to move on from there, again examining the four locations. Repeat the process until you reach the exit of the maze.

You will need a mechanism to keep you from going right back to the location you just came from. There are several ways of doing this. One is to keep a second array in which you mark a location as soon as you visit it. You only go to a location if it is not blocked and has not been visited yet.

You will also need some way of making sure you don't step off the board.

A recursive function to traverse the maze will need a stopping condition and recursive calls. The stopping condition occurs when you reach the exit of the maze. Four recursive calls correspond to the four directions that you can travel. A rough outline is

     traverse (int i, int j)
     {
        if (path not blocked and haven't visited this location yet)
        {
           if (i == n-1 && j == m-1)
              we're out
           else
           {
              visited[i][j] = 1;
              traverse(i-1, j);
              traverse(i, j+1);
              traverse(i+1, j);
              traverse(i, j-1);
           }
        }
     }


This is a barebones outline.  There are many fine details to work out.

Input

The input to the program is the size of the board (n, m) folowed by a sequence of nxm 0s and 1s representing the board. Sample files available here.

Output

As a bare minimum, the program should output whether or not there is a path through the maze. For more credit, output the actual path as a sequence of (i ,j) pairs representing the path.

To do

Write the maze traversal program.