BFS Sample Execution

Be sure to look at the solution so you understand the BFS algorithm.
In this sample execution, we will be solving the maze below.

###.###
.....#.
#.#.##.
#.#....
#.####.
.......
##.####

A number on the maze represents the number of steps required to reach it. We know the start takes zero steps to reach, so let’s fill that in.

###0###
.....#.
#.#.##.
#.#....
#.####.
.......
##.####

Now, the space next to the start is unmarked, so it must require one more step than the start to reach.

###0###
...1.#.
#.#.##.
#.#....
#.####.
.......
##.####

The three spaces next to the 1 are unmarked, so they must each take one more step to reach.

###0###
..212#.
#.#2##.
#.#....
#.####.
.......
##.####

Continuing with this process, we get step that look like this.

###0###    ###0###    ###0###
.3212#.    43212#.    43212#. 
#.#2##.    #4#2##.    #4#2##.
#.#3...    #.#34..    #5#345.
#.####.    #.####.    #.####.
.......    .......    .......
##.####    ##.####    ##.####

Eventally, the exit becomes filled, and the algorithm is done. We know this maze takes 9 steps to solve.

###0###
43212#8
#4#2##7
#5#3456
#6####7
8789.98
##9####