Entering edit mode

Croft and the Relics

In one of her adventures, Lara Croft comes across a maze floating in the sky filled withancient relics. She has a teleporter with her
which will help her to land on the maze from the ground and get back to the ground aftercollecting the relics. There are a couple of
catches though:

The Teleporter has enough power just for 2 teleportations - one for landing on it. and the other for getting back to the groundHence, once she is on the maze, she can use the teleporter only to jump back to the ground and not to jump to any other point in the maze. Which implies on the maze she can only walk from one tile to another and she has no other tricks up her sleeve
The maze is organised as a 2-D grid of tiles where some tiles have obstacles on them and all of the other tiles have 1 ancient relic on them.
From the current ble she is on. she can move only to any of the 4 adjacent tiles if they don't have an obstacie on them
Once she leaves a tile it falls down and thus she cannot go back to tile she has already visited
From ground,she can teleport to any tile on the maze which doesnt have an obstacle on it

Complete the findMaximumRelics function ir the editor below. It has 1 parameter: grid: An array of strings. The cells of which
contain either '*' (denoting that the tile hasrelic) or ' (denoting that the tile has an obstacle).

Input Format

Locked stub code in the editor reads the following input from stdin and passes it to the function:

The first line contains an integer, r, denoting the number of rows of the 2D grid. Then there are r lines . The i^thlines contains a string denoting the configuration of the ith row of the grid . Each character in the string is either a "*"(denoting that the title has a relic) or '.'
(Denoting that the title has an obstacle)

Constraints

is printed to stdout by locked stub code in the editor.

Sample Input 0
2
-*
*-

Sample Output 0

1

Explanation 0

The grid has 2 rows and 2 columns. If Lara starts from the upper right tile she can only visit 1 tile and if she starts from bottom left tile she can again visit tile 1. So the maximum number of tiles she can visit is 1 (which is equal to the relics she an collect)

3. Relay Race

Relay race is a team sport where a baton ispassed from one person to another and eachperson is required to complete their racecourse with the baton and pass it to the next
person. We identify difference racers of ateam with their jersey colors.In this problem, you are given a list of transitions of the baton between different
people (identified by colors of their jerseys) and you are required to find the entire course of transition of the baton between two racers for multiple queries.

More formally you will be given a list of transistion of the form <colour1><colour2> reprsenting thata baton was passed between a racer wearing colour 1 jersey and racer in colour 2 jersey . You will be asked some queries of the format

1. A string array, transitions, which contains the number
of transitions that occurred in the relay race

2. A string array, queries which contains the
queries to be evaluated.

The function must return a string array which the answer to the query array. Each string in the array should be of the format a_i,a_i+1...a_n, where a is the color of the starting racer and aj-ri-2.. are the colors of the intermediate racers and an is the color

of the racer that finally has the baton. The number of steps to transition the baton from a_i to a_n should be minimum possible.

Input Format

Locked stub code in the editor reads the following input from stdin and passes it to the function: The first line contains an integer, n, denoting the
number of transitions. The next n lines contain the transitions. The line after that contains an integer, m, denoting the number of queries. The next m lines contain queries.

Constraints

1<= n <= 55
1 <= m <= 3000

Output Format

The function must return a string array as stated above in the problem description. This is printed to stdout by locked stub code in the editor

Sample Input 0


2
Red-Purple
Purple-Brown
1
Red-Brown


Sample Output 0


Red, Purple, Brown

Explanation 0
The transitions are Red-Purple and Purple-
Brown. The query is Red-Brown. The only way for transistions from
Red to Brown is Red,Purple,Brown. So this is the answer

ADD COMMENT • link