Scenario
Our maze is an H by W rectangle, represented by an array of size H of W-sized strings. Each character in a string can either be '#' or '.'. '#' represents a wall, which we cannot cross, and '.' represents a free space, which we can cross. The border of the maze is always filled with '#' except for one square, which represents the exit. For example, the following is a valid maze:
Find the total number of steps to exit the maze, when supplied with a starting point (i, j) (with (0, 0) being the upper-left point and (H, W) being the lower-right point).
Aim
To use BFS to find the shortest path out of a given maze.
Prerequisites
- Implement the distToExit() method of the Maze class in the source code, which returns the integer distance from that point to the exit of the maze. It is available at the following URL:
https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson6/activity/maze/Maze.java - Assume that the points supplied to distToExit() are valid (that is, they're not inside walls)
- Remember that we can only move in the cardinal directions (North, South,
East, and West)
Steps for Completion
- Encode the maze representation to a graph representation
- Apply the BFS implementation shown in the preceding section (with a small modification to account for distances), or you can build the graph as you go
- Since you know that there are at most four outward edges for a given vertex, compute their positions as you go
In this section, we've introduced two different ways to traverse a graph—breadth-first search (BFS) and depth-first search (DFS). We've seen how to use BFS to find the single-source shortest path in unweighted graphs and how to use DFS to find cycles in a graph. In the next section, we will be looking at two different algorithms to find shortest paths in a graph.