Only answer part a) [10] In a rectangular field of size m by n squares there is

Question

Only answer part a)

[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) (m,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), (rL,CL): The coordinates of the initial squares where Sushant. Dan and Larry start from. . 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

Explanation / Answer

Each of square in the grid represents a node in a graph. Connected horizontal and vertical squares represent an edge but if there is an obstacle then it is not a edge.

So to uniquely determine every node you can number the nodes(squares) from 0 to m*n-1. Then a number S represents in zero based indexing:

ROW: S / n

COLUMN: S % n

Ex: m = 4, n = 5, So for 10 it becomes row=10/5=2, column=10%5=0

Here is / is integer division and % is modulo operator. Above you can see that 10 if zero based indexing is used then it is in 3rd row(2 if zero based indexing) and 1st column(0 if zero based indexing).

So now when naming of nodes is done make edges on nodes by having 4 edges.

For node S: (S-1), (S+1), (S+n), (S-n).

Only have to check corner case when S is representing border. Also don't put edge if and node is in obstacle.

So check if S = 0/n-1/m-1(zero based indexing) then make 2 edges instead of 4.

For C++ you can use vector<vector<int>>. Time complexity is n*m as need to go to all the nodes add edges to vector and also check if it is obstacle.

Please rate the answer. This solution will work if needs more explanation then please comment on it. Also description was asked so code not provided

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.