Super Mario Run A Mario world M consists of a k × k grid. Each field in the grid is either empty or brick. Twoempty fields are marked as start and goal (see Fig. 2(a)). The goal of the game is to move the player, called Mario, fromthe 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 bedone 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 correspondto a vertex and the valid moves define the edges (there is an edge from field (x, y) to field (x′, y′) if Mario can movefrom (x, y) to (x′, y′) with a valid move). The edges corresponding to forward, jump and fall are denoted by forwardedges, jump edges and fall edges. We are interested in checking if it is possible to go from the start field to the goal field. A Mario graph is validif there exists a path from start to goal. Give an algorithm in pseudo code that given a Mario graph G, decides whether or not there is apath from the start field to the goal field. Analyze the running time of your algorithm in the relevant parameters of theproblem. We are also interested in collecting a mushroom during the game. A mushroom graph is a valid Mario graph where asingle node c is marked as a mushroom node and there is a path from start to goal that goes through c. Give an algorithmwhich, given a mushroom graph, finds a cheapest path from the start to the goal that goes through c. Analyze the runningtime of your algorithm in the relevant parameters of the problem.

Please login or Register to submit your answer