The Maze Path Problem

Given a rectangular maze stored as a char[][], determine whether there is a path from the top-left cell to the bottom-right cell. A cell is blocked if it contains '#'. From a cell, you may move one step up, right, down, or left, but you may not leave the maze or move into a wall.

For the rest of the chapter, we will assume the start is the top-left cell, (0, 0), and the exit is the bottom-right cell, (rows - 1, cols - 1). This is only a convention. Where the start and exit are does not change how the search works, and we could pass their coordinates as parameters instead. Fixing them to the corners keeps the method signatures short. We will still draw the start and exit as S and E in examples, because that makes the pictures easier to read.

Here is one maze with a path, marked with •. Starting from S, the path goes right twice along the top row, then down two cells, and finally right into the exit:

┌───┬───┬───┬───┐
│ S │ • │ • │ █ │
├───┼───┼───┼───┤
│ █ │ █ │ • │ █ │
├───┼───┼───┼───┤
│   │   │ • │ E │
└───┴───┴───┴───┘

Here is another maze with no path:

┌───┬───┬───┬───┐
│ S │   │ █ │   │
├───┼───┼───┼───┤
│ █ │   │ █ │   │
├───┼───┼───┼───┤
│   │   │ █ │ E │
└───┴───┴───┴───┘

The start can reach the open cells on the left side, but the wall column blocks every path to the exit on the right.

Before we write the code, let me name a few edge cases:

  • If the start cell is a wall, there is no path.
  • If the exit cell is a wall, there is no path.
  • If the maze has one cell and that cell is open, the start is already the exit.
  • A path is allowed to turn and revisit a row or column, but the search should not keep revisiting the same cells forever.

These edge cases are simple to state because the start and exit are fixed by position. The character in a cell only says whether the cell is open or a wall. Suppose instead that the search found the start and exit by looking for S and E in the array. Then a one-cell maze could not hold both S and E. A start or exit could not also be a wall. And we would need to handle a maze with no S or no E, or with more than one of each. Those are more edge cases, and none of them is about finding a path. This is why we fix the start and exit by position.