4. [10] In a rectangular field of size m by n squares there is Dan, Larry and Sushant. They are playing a game called "Catch Larry" which has the following rule: Each of Larry, Dan and Sushant starts off at some initial square, then Larry is the first to make a move, then each of Sushant and Dan makes a move, then again it's Larry's turn, and so on. In each move, all three of them can move exactly one square vertically or horizontally, and they cannot move into a square that is an obstacle (the grey squares in the picture). If Larry is standing at the edge of the field (the yellow zone) then in his next move he can Jump off the field and safely escape from Sushant and Dan's chase, i.e., Larry wins. If after any move Sushant or Dan moves to the square which Larry is in, they catch Larry, i.e., Sushant and Dan win (2,n) Your job is to develop an efficient algorithm with the following input and output Input: The values of m and n. . (rs, cs), (rD,cD), (ri,cL): The coordinates of the initial squares where Sushant, Dan and Larry start from, respectively A list of coordinates of the squares that are obstacles Output: . whether there exists an escape path for Larry, i.e., if Larry follows this path, he will be able to successfully escape for sure, regardless of how Sushant and Dan move Assumptions: . The obstacles are placed in such a way that it is possible to move from any non-obstacle square to any other non-obstacle square of the field Describe the design of your algorithm by answering the following questions (a) Describe how to construct a graph to solve this problem. More precisely, describe the detailed procedure of creating the adjacency list of the graph from the given input. Clearly indicate which data structures you use. Analyze the runtime of your graph construction procedure. (b) Given the graph that is constructed in Part (a), how do you efficiently determine whether there exists an escape path for Larry? Describe your algorithm in concise (but precise) English, and analyze its runtime