Problem Description

There is a robot that can help fetch coffee to staffs in an office. Now, suppose you are developing an algorithm for this robot to achieve this task. Please look at the office map below. On the map, the number represents the ID of a Tile. The solid lines represent impenetrable walls.

At the start, this robot is at Tile $1.$ Please help the robot fetch the coffee at the Tile $20$ by planning a route for it based on the state$-$space searching algorithms we have learned. $(1)$

Please discuss how you can solve this problem by using depth$-$first search $($DFS$)$ algorithm. Please write down step by step procedure of the searching algorithm, as well as the final solution searched by DFS$.(7$ marks for step by step procedure, $5$ marks for solution$)$

$(2)$

Please discuss how you can solve this problem by using breadth$-$first search $($BFS$)$ algorithm. Please write down step by step procedure the searching algorithm, as well as the final solution searched by BFS$.(7$ marks for step by step procedure, $5$ marks for solution$)$

$(3)$ Please discuss the advantages and disadvantages of DFS$,$ and BFS search regarding this problem. $(6$ marks for discussions$)$