Figure $2$

Question $2[6$ pts$]$ Figure $2$ shows a robot navigation field, where the green square $($b$7)$ is the

robot, and red square $(d2)$ is the goal. The shad squares $($such as $c2,d3$ etc.$)$ are obstacles. The

robot is not allowed to move in diagonal line. Nodes are coded using an alphabet letter followed

by a digit $($such as $b1,b2$ etc.$).$ When two sibling nodes are inserted into fringe $($queue$),$ use

deque order to favor node with a lower alphabet and a lower digit. For example, if d$1$ and e$2$ are

sibling nodes, $d1$ will be dequeued first $($because $"d"$ has a lower alphabetic order than $"$e$").$ If e$1$

and e$2$ are sibling nodes, e$1$ will be dequeued first $($because $"1"$ has a lower digit than $"2").$ Node

expanded$/$visited does not need to be revisited.

Use Depth First Search to find path from b$7$ to d$2.$

Report nodes $in$ the fringe $in$ the orders they are included $in$ the fringe.

$[0\mathrm{.}5pt]$

Report the order $of$ the nodes being expanded. $[0\mathrm{.}5pt]$

Report the final path from $b7tod2.[0\mathrm{.}5pt]$

Depth First Search