The $5$x$5$ maze below represents a sample boulder field. The $\text{'}1\text{'}$ values represent boulders and the $\text{'}0\text{'}$ values represent paths between.

Using the algorithm below, show the resulting path with $\text{'}$X$\text{'}$ characters for the $7$x$7$ maze. Mark backtracking with $\text{'}$#$\text{'}$ characters.

Your search will begin at row $0$ column $0,$ represented as coordinates $(0,0).$ You are aiming for row $6,$ column $6$ or $(6,6).$

$***$Pseudo Code Algorithm for a Depth First Search $***$

Create an empty search queue for positions yet to explore, add the entrance $(0,0),$ to the queue

Create an empty stack to hold the path of coordinates

While the search list is not empty

Remove the next position from the search queue

If it is the exit position, $($n$-1,$ n$-1),$

then a path is found

Otherwise, mark the position as visited $($use an $\text{'}$X$\text{'}),$ push the position on the stack,

and add all valid right, down, left, or up neighbor positions to the search queue $($in that order$)$

While the next position in the search queue is not adjacent to the position on the top of the stack, pop the stack and

mark the position as backtracked $($use a $\text{'}$#$\text{'})$

If the search queue is empty and the current position is not the goal position, there is no path

$------------------------------------------------------$

Example $5$x$5$ boulder maze and solution:

$01010$

$00010$

$01000$

$01011$

$01000$

$5$x$5$ solution:

start$--->$ X $101$ #

X X X $1$ #

$01$ X # #

$01$ X $11$

$01$ X X X $--->$ goal