Find Path Through a Maze

We can extend the prior problem to find the path through the maze. You can think of this problem as the grid problem, but with an added constraint. The constraint is this-- that some cells of the maze are not accessible at all, so the robot cannot step into those cells.

Let's call these "inaccessible" cell pits, where the robot is forbidden to enter. The paths that go through these cells should then be abandoned earlier on in "the search". The pseudo-code thus remains the same with one additional base case, which is to stop if the cell is a forbidden cell.

xxxxxxxxxx

routine: enumerateMaze

input: Grid m * n

output: Display all paths

assumption: result is empty to begin with

​

Base case 1:

1. If target is reached then print the path

Base case 2:

2. If left or right cell is outside the maze then stop

Base case 3:

3. If the cell is a pit then stop

​

Recursive case:

1. Add the current cell to path

2. Invoke enumerateMaze to find all paths that are possible by doing an "up" move

3. Invoke enumerateMaze to find all paths that are possible by doing a "right" move

4. Remove the current cell from path