4. [10] In a rectangular field of size m by n squares there is Dan, Larry and Su

Question

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

Explanation / Answer

ANSWER

GIVEN BY

every of square in the grid represent a node in a chart.

Connected flat and perpendicular squares represent an edge but if present is an obstacle after that it is not a edge.

So to uniquely decide every node you can figure the nodes(squares) from 0 to m*n-1. Then a numeral S represent in zero base indexing:

ROW: S / nCOLUMN: S % n

Ex: m = 4,

n = 5,

So for 10 it become row=10/5=2,

column=10%5=0

Here is / is integer separation and % is modulo operator.

Above you can observe that 10 if zero based indexing is used next it is in 3rd row(2 if zero base indexing) and 1st article(0 if zero based indexing).

So now when identification of nodes is done create edges on nodes by have 4 edges.

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

Only encompass to check corner case while S is representing limit

Also don't put rim if and swelling is in obstacle.So check if S = 0/n-1/m-1(zero based indexing) then make 2 edges in its place of 4.

For C++ you can make use of vector>. Time complexity is n*m as call for to go to all the nodes insert edges to vector as well as also verify if it is obstacle.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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