(a) There is a robot in the Gridville neighborhood, as well as houses and open plots. The robot can move in all the four directions, i.e left, right, up and down, but can only go over the open plots, and once the robot starts to move in one direction it wont stop until it hits a house. The robot may changes its direction after it stops. Given the map of the neighborhood, the starting location of the robot, and a final location, describe and analyze an algorithm to determine if the robot can reach the final location. You may assume that the neighborhood is completely surrounded by houses.

(b) For the above question describe and analyze an algorithm to find the length of the shortest path the robot can take from start to finish. The distance is measured by the number of open plots the robot goes over from the start position (not included) to final position (included). If there is no such path say so.

Ex: For Fig A the length of the shortest path is 12 - (left(1) ? down(1) ? left(3) ? down(1) ? right(2) ? down(2) ? right(2)). In Fib B you dont have a shortest path

(c) Describe and analyze an algorithm to find a shortest path the robot can take from start to the final location. As before, the distance is measured by the number of open plots the robot goes over from the start (not included) to the final position (included). Return the sequence of directions the robot should take along a shortest path using the letters l, r, u and d, which represent left, right, up and down, respectively. If there are multiple such paths, return the output that comes first in the lexicographical ordering. If there is no such path say so.

Ex: In Fig D there are two possible shortest paths to reach the final location, ul and lul each of which are of length 6. So you must return lul since l

Fig A Fig B Fig C Ex: For Fig A, there is a path such that the robot can reach the green tile (its final location). Namely, see the orange path shown in Fig C (left ? down ? left ? down ? right ? down ? right). For the input in Fig B, it is not possible for the robot to stop at the final location Fig A Fig B Fig C Ex: For Fig A, there is a path such that the robot can reach the green tile (its final location). Namely, see the orange path shown in Fig C (left ? down ? left ? down ? right ? down ? right). For the input in Fig B, it is not possible for the robot to stop at the final location