Question

2 Super Mario Run A Mario World M consists of a k xk grid. Each field in the grid is either empty or brick. Two empty fields are marked as start and goal (see Fig. 2(a)). The goal of the game is to move the player, called Mario, from the start field to the goal field. When Mario is in field (x,y) he has the following options: Forward Mario moves to the field (x + 1,y). This move is possible if (x +1, y) is empty and (x+1, y-1) is brick. Jump Mario moves to the field (x +1, y + 2). This move is possible if the fields (x, y + 2), (x,y+1), and (x+1, y +2) are empty, and (x+1, y +1) is brick. Fall Mario moves to the field (x + 1, y') where y' <y is the maximal value y such that (x + 1, y'-1) is brick and (x +1,y),(x+1, y-1),..., (x+1, y) are empty For instance, Mario in field (4,4) can move forward to (5, 4) or jump to field (5,6). A move is valid if the move can be done according to the above rules. All fields that can be reached via valid moves from the start field are the valid fields. For example, (4,4) is a valid field, since it can be reached from the start field in (1, 2) doing the sequence of valid moves: forward, forward, jump. A Mario World M defines a directed graph G with n vertices and m edges (see Fig. 2(b)). All valid fields correspond to a vertex and the valid moves define the edges (there is an edge from field (x,y) to field (x, y) if Mario can move from (x,y) to (x,y) with a valid move). The edges corresponding to forward, jump and fall are denoted by forward edges, jump edges and fall edges. Below: "Give an algorithm" means describe it using words, not actually code for the algorithm.

Answer 1

1. Since the above scenario can be translated to a Directed graph with V vertices (V = n*m) and M edges (M = total possible moves).

We need to find path, if it exists, from one vertex to another in the graph.

We can use the Breadth First Search (BFS) or Depth First Search (DFS) to find if there exists a path by starting from one vertex and check if other one comes during the search.

Description of BFS

Let Q be a queue, S be the starting vertex and D be the destination vertex

For all the vertices that are directly connected to S, insert them into the Q

Now for all the vertices in Q, check if D is one of them. If it is, then path exists else repeat the same process as done with the starting vertex i.e. insert all the vertices that are connected to it and havent been visited yet, to the queue.

In the end, if D is not encountered then report that path does not exists else path exists.

Time Complexity = O(V+E) = O(k^4) where k is the side of the grid.

V is O(k*k) since there can be k*k vertices at max

E is O(k^4) since there can be at max k*(k-1)/2 edges