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. 2.3 We are now interested in checking if it is possible to go from the start field to the goal field. A Mario graph is valid if there exists a path from start to goal. Give an algorithm that given a Mario graph G, decides whether or not there is a path from the start field to the goal field. Analyze the running time of your algorithm in the relevant parameters of the problem.

Answer 1

Algorithm:

1. Assuming a k*k matrix in the form of 0's and 1's, where 0 denote empty space and 1 denotes brick.
2. Now we start from start point given. We will be traversing through Breadth First Search algorithm.
3. For each coordinate from where we are passing on we will be applying each travelling option (forward, jump, fall) one by one.
4. For each option we will be checking if it satisfies the given rules and takes Mario to a valid position. If a valid position is found we will be adding its coordinates to a queue(storing pair as x coordinates and y coordinates).
5. Once all options for that particular coordinates are dealt with we will be poping stored coordinates from queue and then applying the same procedure to it.
6. There may be a situation when we haven't reached our destination but our queue is empty. This simply means that there is no valid path after that. So,no path between start and destination point.
7. If we are able to reach destination coordinates we will be printing "Path found".

Time complexity: O(k^2)