Programming Geek
Rated 4.7/5 based on 1446 reviews

Longest Possible Route: TCS CodeVita 2016 Question

No comments :
Problem : Longest Possible Route



Given an MxN matrix, with a few hurdles arbitrarily placed, calculate the cost of longest possible route from point A to point B within the matrix.
Input Format:
  1. First line contains 2 numbers delimited by whitespace where, first number M is number of rows and second number N is number of columns
  2. Second line contains number of hurdles H followed by H lines, each line will contain one hurdle point in the matrix.
  3. Next line will contain point A, starting point in the matrix.
  4. Next line will contain point B, stop point in the matrix.

Output Format:

Output should display the length of the longest route from point A to point B in the matrix.
Constraints:
  1. The cost from one position to another will be 1 unit.
  2. A location once visited in a particular path cannot be visited again.
  3. A route will only consider adjacent hops. The route cannot consist of diagonal hops.
  4. The position with a hurdle cannot be visited.
  5. The values MxN signifies that the matrix consists of rows ranging from 0 to M-1 and columns ranging from 0 to N-1.
  6. If the destination is not reachable or source/ destination overlap with hurdles, print cost as -1.


Sample Input and Output


SNo.InputOutputExplaination
1
3 10
3
1 2
1 5
1 8
0 0
1 7 

24

Here matrix will be of size 3x10 matrix with a hurdle at (1,2),(1,5 ) and (1,8) with starting point A(0,0) and stop point B(1,7)

3 10
3 -- (no. of hurdles )
1 2
1 5
1 8
0 0 -- (position of A)
1 7 -- (position of B)

So if you examine matrix below shown in Fig 1, total hops

( ->) count is 24. So final answer will be 24. No other route longer than this one is possible in this matrix. 
2
2 2
1
0 0
1 1
0 0 

-1

No path is possible in this 2*2 matrix so answer is -1








ISL Schedule: TCS CodeVita 2016 Question

No comments :
Problem : ISL Schedule




The Indian Soccer League (ISL) is an annual football tournament.
The group stage of ISL features N teams playing against each other with following set of rules:
  1. N teams play against each other twice - once at Home and once Away
  2. A team can play only one match per day
  3. A team cannot play matches on consecutive days
  4. A team cannot play more than two back to back Home or Away matches
  5. Number of matches in a day has following constraints
    • The match pattern that needs to be followed is -
      • Day 1 has two matches and Day 2 has one match,
      • Day 3 has two matches and Day 4 has one match and so on
    • There can never be 3 or more matches in a day
  6. Gap between two successive matches of a team cannot exceed floor(N/2) days where floor is the mathematical function floor()
  7. Derby Matches (any one)
    • At least half of the derby matches should be on weekend
    • At least half of the weekend matches should be derby matches
Your task is to generate a schedule abiding to above rules. 

Input Format:

First line contains number of teams (N).
Next line contains state ID of teams, delimited by space
Output Format:

Match format: Ta-vs-Tb
where Ta is the home team with id a and Tb is the away team with id b.
For each day print the match(es) in following format:-
  • Two matches:- "#D Ta-vs-Tb Tm-vs-Tn"
  • One match:- "#D Tx-vs-Ty"
where D is the day id and [a, b, m, n, x, y] are team ids. 

Constraints:
1. 8 <= N <= 100
Note : 
  • Team ids are unique and have value between 1 to N
  • Day id starts with 1
  • Every 6th and 7th day are weekends
  • Derby is a football match between two teams from the same state

Sample Input and Output


SNo.InputOutput
1
8
1 2 5 4 3 1 6 6

#1 T1-vs-T6 T3-vs-T5
#2 T7-vs-T4
#3... and so on


Note:- There can be multiple correct answers for the same test cases. For better understanding of test case refer this 
PDF. This PDF contains one of the correct answer for a test case. 

Explanation:

There are 8 teams with following information:- 

Team ID12345678
State ID12543166

Calculate Salary And PF: TCS CodeVita 2016 Question

No comments :
Problem : Calculate Salary And PF





Statement :

Calculate the Final Salary & Final Accumulated PF of an Employee working in ABC Company Pvt. Ltd. The Company gives two Increments (i.e. Financial Year Increment & Anniversary Increment) to an Employee in a Particular Year.

The Employee must have Completed 1 Year to be Eligible for the Financial Year Increment. The Employee who are joining in the month of Financial Year Change (i.e. April) are considered as the Luckiest Employee's, because after completion of 1 Year, they get Two Increments
(Financial Year Increment & Anniversary Increment).

Rate of Interest for the Financial Year Increment = 11%.
Rate of Interest for the Anniversary Increment = 12%.

From 4th Year, the Financial Year Increment will be revised to 9%.
From 8th Year, the Financial Year Increment will be revised to 6%.
The Company is giving special Increment for the Employee who have completed 4 years & 8 years respectively.

So, the Anniversary Increment of the Employee for the 4th Year will be 20% and the Anniversary Increment of the Employee for the 8th year will be 15%.

Calculate the Final Salary after N number of Years as well as Calculate the Accumulated PF of the Employee after N number of Years.

Please Note that, the Rate of Interest for calculating PF for a Particular Month is 12%. Moreover, take the upper Limit of the amount if it is in decimal (For e.g. - If any Amount turns out to be 1250.02, take 1251 for the Calculation.)
Input Format: 
  1. Joining Date in dd/mm/yy format
  2. Current CTC.
  3. Number of Years for PF & Salary Calculation.

Output Format:
  1. Salary after the Specified Number of Years (i.e. CTC after N number of Years) in the following format
    Final Salary =
  2. Accumulated PF of the Employee after N number of Years in the following format
    Final Accumulated PF =


Constraints:
  1. Calculation should be done upto 11 digit precision and output should be printed with ceil value

Sample Input and Output


SNo.InputOutput
1
5
01/01/2016
10000
2

Final Salary = 13924
Final Accumulated PF = 2655
2
19/01/2016
6500

Final Salary = 14718
Final Accumulated PF = 4343


Area Of The Crazy Ring: TCS CodeVita 2016 Question

No comments :
Problem : Area Of The Crazy Ring




Scientists have found a strange substance having strange properties. There is one triangular substance called Strange Triangle which has a property that if it is placed inside a circle then it expands until all the corners of the triangle are touching the circle. There is another circular substance called Strange Circle, which when placed inside any polygon, expands such that it becomes the largest possible circle which can fit inside the polygon such that it touches every side of the polygon.
Strange Triangle: 


Strange Circle: 


Now researchers did a strange experiment. They placed a Strange Triangle inside a normal circle and then placed a Strange Circle inside this Strange Triangle. Thus the ring formed by the two circles, the normal outer circle and the inner strange circle is named Crazy Ring. You are provided with the coordinates of the Strange Triangle on coordinate plane and you have to calculate the area of the Crazy Ringformed by the structure, Print "Not Possible" if the ring is not possible to form.

Input Format:
  1. First line contains two space delimited numbers N1 M1 (N1 and M1 can also be negative)
  2. Second line contains two space delimited numbers N2 M2 (N2 and M2 can also be negative)
  3. Third line contains two space delimited numbers N3 M3 (N3 and M3 can also be negative)
Where, (N1, M1) , (N2, M2) and (N3, M3) are x and y coordinates of three points representing the Strange Triangle

Output Format:

Output the area of the crazy ring up to 2 decimal places however calculations are to be performed up to a precision of 11 decimal places

OR

Print "Not Possible" if it is not possible to form the ring
Sample Input and Output


SNo.InputOutput
1
5 5
5 20
20 5 

292.79 
2
5 5
5 5
5 5 

Not Possible
3
5 8
4 3
2 4.34534554521 

17.91

Rook Moves: TCS CodeVita 2016 Round1 Question

No comments :
Problem : Rook Moves



Background

A Chess board position is accurately captured by Forsyth-Edwards notation and is abbreviated as FEN. A FEN "record" defines a particular game position, all in one text line and using only the ASCII character set. A FEN record contains six fields. A complete description of the FEN format to represent Chess positions can be found at here

For the purpose of this problem only consider first of the six fields of FEN. Before we describe the problem, let us look at how FEN maps to a board position. The following 5 images show board positions and its corresponding FEN representation.

                    Figure 1.




This board position depicts initial position before any side has made a move. In FEN format this board position is represented as


rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w















Let's say, White plays e4. Then the board position looks like shown below


                    Figure 2.




This board position depicts the Chess board after White has played e4. In FEN format this board position is represented as


rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b















Similarly, 3 more half-moves are depicted in following diagrams

Figure 3.

 
Figure 4.

  
Figure 5.

The FENs corresponding to Figure 3, 4 and 5 are represented as

           3. rnbqkbnr/pppp1ppp/8/4P3/4P3/8/PPPP1PPP/RNBQKBNR w
           4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR b
           5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR w

Wikipedia describes first field of FEN format as follows

Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file "a" through file "h". Following the Standard Algebraic Notation (SAN), each piece is identified by a single letter taken from the standard English names (pawn = "P", knight = "N", bishop = "B", rook = "R", queen = "Q" and king = "K").[1] White pieces are designated using upper-case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks.

The second field denotes whose move it is now. "w" depicts that it is White's turn to play and "b" indicates that it is Black's turn to play

CodeVita Problem Statement

Given a board position in FEN format, your task is to find out all the move(s) that Rook(s) of the playing side can make.

Input Format:
  1. First line contains single FEN record, which corresponds to a particular board position and also indicates whose turn it is.

Output Format:
  1. The output must be printed as follows
    1. All legal moves that Rook(s) can make must be in the format "[]"
    2. Where is move represented in format "[fromSquare][toSquare]"
  2. See Example section for better understanding of output format
  3. Follow Output printing specification to print the output in required format

Constraints:
  1. Since we focus on only first two parts of the FEN, we are essentially ignoring possibility of Castling. Hence our test cases don't contain FENs which give rise to such positions.

Sample Input and Output


SNo.InputBoard DepictionOutput
1
2k5/8/8/3B4/2PRN3/3B4/8/4K3 w


[]
2
2k5/2p5/8/8/2PRN3/8/8/2K5 w


[d4d8, d4d7, d4d6, d4d5, d4d3, d4d2, d4d1]
3
3k4/2pp4/8/8/RR6/8/8/1K6 b


[a4a8, a4a7, a4a6, a4a5, a4a3, a4a2, a4a1, b4b8, b4b7, b4b6, b4b5, b4c4, b4d4, b4e4, b4f4, b4g4, b4h4, b4b3, b4b2]

Print Specification:
  1. Should start with "[" and end with "]"
  2. If more than one move is possible, moves should be separated by a comma followed by whitespace
  3. Moves of a single bishop should be printed in Move Format. Scan the board from 8th rank to 1st rank from a-file to h-file. Whichever square gets hit first, that move should be printed first.
  4. If more than one bishop exists for side to move, then start scanning for bishop from 8th rank to 1st rank, left to right i.e. from a-file to h-file. Whichever bishop appears first, print all moves for that bishop first.
  5. Verify your understanding of how printing should happen against examples shown above


House Numbers: TCS CodeVita 2016 Round1 Question

No comments :
Problem : House Numbers



There are a number of buildings of different sizes (width) and with different number of floors. Each may have zero, one or more flats marked with a different character, say $. Identify these flats and print the address in form of building number, floor and flat number.

Buildings are separated from each other by a space character. Floors start from 1 i.e. the lowest floor is the first floor. Also flat numbers are assigned from left to right. The $ character is the flat of interest for which we have to find the address.

For example,


The above is an example of a colony with 4 buildings. The first building has 5 floors with 4 flats on each floor. The flat marked by $ in the first building can be identified as 134 (building 1, floor 3 and flat 4). Similarly, the flat marked by $ in the second building can be identified as 223 (building 2, floor 2 and flat 3).

A file containing a random colony will be given as an input to your program. You have to identify all flats marked by $ in the colony. Note that there is no limit to the number of buildings, floors or flats.
Input Format:

Text file path
Output Format:

Print Building number(B), floor number(F), Flat numbers(R) of all flats marked by $ in the following format:

Constraints:
Print order for $-marked flats should be from top floors to bottom floors and left building to right building

Sample Input and Output


SNo.InputContents Of Input FileOutput
1/tmp/T1.txt
232
2/tmp/T2.txt
>
152
142
341
221
223
111
213



Exam Efficiency: TCS CodeVita 2016 Round1 Question

No comments :
Problem : Exam Efficiency



In an examination with multiple choice questions, the following is the exam question pattern.
  • X1 number of One mark questions, having negative score of -1 for answering wrong
  • X2 number of Two mark questions, having negative score of -1 and -2 for one or both options wrong
  • X3 number of Three mark questions, having negative score of -1, -2 and -3 for one, two or all three options wrong
  • Score Required to Pass the exam : Y
  • For 1,2 and 3 mark questions, 1,2 and 3 options must be selected. Simply put, once has to attempt to answer all questions against all options.
Identify the minimum accuracy rate required for each type of question to crack the exam.

Calculations must be done up to 11 precision and printing up to 2 digit precision with ceil value

Input Format:

First line contains number of one mark questions denoted by X1,
Second line contains number of two mark questions denoted by X2
Third line contains number of three mark questions denoted by X3
Fourth line contains number of marks required to pass the exam denoted by Y.
Output Format:

Minimum Accuracy rate required for one mark question is 80%
Minimum Accuracy rate required for Two mark question is 83.33%
Minimum Accuracy rate required for Three mark question is 90%


Note: - If the mark required to pass the exam can be achieved by attempting without attempting any particular type of question then show message similar to, One mark question need not be attempted, so no minimum accuracy rate applicable

See Example Test cases for better understanding.

Sample Input and Output


SNo.InputOutputExplaination
1
20
30
30
120

One mark questions need not be attempted, so no minimum accuracy rate applicable.
Minimum Accuracy rate required for Two mark question is 58.33%
Minimum Accuracy rate required for Three mark question is 72.23% 

If one got full marks in two marks question and three marks question then total accuracy can be 0 in one mark question

In same way it will be done for two marks and three marks question
2
20
30
30
170

Minimum Accuracy rate required for one mark question is 100%
Minimum Accuracy rate required for Two mark question is 100%
Minimum Accuracy rate required for Three mark question is 100% 

If one got full marks in two marks question and three marks question then total accuracy should be 100% in one mark question to pass the exam.

In same way it will be done for two marks and three marks question

Christmas Tree: TCS CodeVita 2016 Round1 Question

No comments :
Problem : Christmas Tree


Chirag is a pure Desi boy. And his one and only dream is to meet Santa Claus. He decided to decorate a Christmas tree for Santa on coming Christmas. Chirag made an interesting Christmas tree that grows day by day.

The Christmas tree is comprised of the following
  1. Parts
  2. Stand
Each Part is further comprised of Branches. Branches are comprised of Leaves.

How the tree appears as a function of days should be understood. Basis that print the tree as it appears on the given day. Below are the rules that govern how the tree appears on a given day. Write a program to generate such a Christmas tree whose input is number of days.

Rules:

  1. If tree is one day old you cannot grow. Print a message "You cannot generate christmas tree"
  2. Tree will die after 20 days; it should give a message "Tree is no more"
  3. Tree will have one part less than the number of days.
    E.g.
    On 2nd day tree will have 1 part and one stand.
    On 3rd day tree will have 2 parts and one stand
    On 4th day tree will have 3 parts and one stand and so on.
  4. Top-most part will be the widest and bottom-most part will be the narrowest.
  5. Difference in number of branches between top-most and second from top will be 2
  6. Difference in number of branches between second from top and bottom-most part will be 1
Below is an illustration of how the tree looks like on 4th day



Input Format:

First line of input contains number of days denoted by N
Output Format:

Print Christmas Tree for given N

OR

Print "You cannot generate christmas tree" if N <= 1

OR

Print "Tree is no more" if N > 20
Constraints:
  1. 0<= N <=20

Sample Input and Output


SNo.InputOutput
12

TCS CodeVita 2016 Round1 Question: Logic Pyramid

No comments :
Problem : Logic Pyramid



Identify the logic behind the series

6 28 66 120 190 276....

The numbers in the series should be used to create a Pyramid. The base of the Pyramid will be the widest and will start converging towards the top where there will only be one element. Each successive layer will have one number less than that on the layer below it. The width of the Pyramid is specified by an input parameter N. In other words there will be N numbers on the bottom layer of the pyramid.

The Pyramid construction rules are as follows
1.    First number in the series should be at the top of the Pyramid
2.    Last N number of the series should be on the bottom-most layer of the Pyramid, with Nth number being the right-most number of this layer.
3.    Numbers less than 5-digits must be padded with zeroes to maintain the sanctity of a Pyramid when printed. Have a look at the examples below to get a pictorial understanding of what this rule actually means.
Example

If input is 2, output will be

 00006
00028 00066

If input is 3, output will be

  00006
 00028 00066
00120 00190 00276

Formal input and output specifications are stated below 
Input Format: 

First line of input will contain number N that corresponds to the width of the bottom-most layer of the Pyramid 
Output Format: 

The Pyramid constructed out of numbers in the series as per stated construction rules 
Constraints:
1.    0 < N <= 14


Sample Input and Output
SNo.
Input
Output
1
2

https://www.tcscodevita.com/CodevitaV5/images/pyramid2.png
2
3

https://www.tcscodevita.com/CodevitaV5/images/pyramid1.png


Pseudo Code: 
The series is subset of Hexagonal Number generated using formula: n * ( 2 * n -1 )

If n is only even number then you will get the series as 6, 28, 66, 120, 190, 276, 378,  496, 630, 780, 946, 1128, 1326, 1540 and so on.

1. for i = 0 to i  < N; i++
    a. print blank space for (N- i - 1) times
    for j = 0 to j <= i ; j++ 
            a. n = ( i + j +1 ) * 2 
        b. num =  n  * ( 2 * n  - 1 )  
        c. if number of digit in num < 5
               print 0 for (number of digit in num - 5) times
        d. print num
        e. if (  j < i )
               print space







TCS CodeVita 2016 Round1 Question: Consecutive Prime Sum

No comments :
Problem : Consecutive Prime Sum



Some prime numbers can be expressed as Sum of other consecutive prime numbers.
For example

5 = 2 + 3
17 = 2 + 3 + 5 + 7
41 = 2 + 3 + 5 + 7 + 11 + 13

Your task is to find out how many prime numbers which satisfy this property are present in the range 3 to N subject to a constraint that summation should always start with number 2.

Write code to find out number of prime numbers that satisfy the above mentioned property in a given range.

Input Format:

First line contains a number N
Output Format:

Print the total number of all such prime numbers which are less than or equal to N.
Constraints:
1. 2

Sample Input and Output


SNo.InputOutputComment
1202
(Below 20, there are 2 such numbers: 5 and 17).
5=2+3
17=2+3+5+7
2151



Pseudo Code:

1. Find all the prime numbers till N
    i.  A  is an array length N + 1 initialized with numbers from 0 to N                 (0,1,2, ..., N)
    ii. initialize p = 2
        a.  for p = 2 to p * p <= N ; p++
               if A[p] != 0 then
                  for  i = p * 2; i <= N; i += p
                         A[i] = 0 // mark non prime as 0
2.  sum = 5, count = 0
3. for j = 5 to j <= N;  j = j+2
    i.  if  ( (A[j]  != 0 && A[j] = sum) || A[j] = -1)
        count = count + 1
    ii. if (A[j] != 0 || A[j] == -1)
        sum = sum + j
        if ( A[sum] != 0) // if A[sum] is prime
            A[sum] = -1 // mark A[sum] as sum of consecutive
4. print count


TCS CodeVita 2016 Round1 Question: Min Product Array

No comments :


The task is to find the minimum sum of Products of two arrays of the same size, given that k modifications are allowed on the first array. In each modification, one array element of the first array can either be increased or decreased by 2.

Note- the product sum is Summation (A[i]*B[i]) for all i from 1 to n where n is the size of both arrays
Input Format: 
  1. First line of the input contains n and k delimited by whitespace
  2. Second line contains the Array A (modifiable array) with its values delimited by spaces
  3. Third line contains the Array B (non-modifiable array) with its values delimited by spaces

Output Format:

Output the minimum sum of products of the two arrays
Constraints:
  1. 1 ≤ N ≤ 10^5
  2. 0 ≤ |A[i]|, |B[i]| ≤ 10^5
  3. 0 ≤ K ≤ 10^9



Sample Input and Output


SNo.InputOutput
1
3 5
1 2 -3
-2 3 -5

-31
2
5 3
2 3 4 5 4
3 4 2 3 2

25

Explanation for sample 1:

Here total numbers are 3 and total modifications allowed are 5. So we modified A[2], which is -3 and increased it by 10 (as 5 modifications are allowed). Now final sum will be
(1 * -2) + (2 * 3) + (7 * -5)
-2 + 6 - 35
-31

-31 is our final answer.

Explanation for sample 2:

Here total numbers are 5 and total modifications allowed are 3. So we modified A[1], which is 3 and decreased it by 6 (as 3 modifications are allowed).
Now final sum will be
(2 * 3) + (-3 * 4) + (4 * 2) + (5 * 3) + (4 * 2)
6 - 12 + 8 + 15 + 8
25

25 is our final answer. 

Simplified Pseudo Code:

1. Initialize maxDiff = 0, minimumSum = 0
2. For i to n
    i. product = A[i] * B[i]
    ii. if ( product < 0 && B[i] < 0 ) then
            temp = (A[i] +  2  * k ) * B[i]
        else if( product < 0 && A[i] < 0) then
            temp = (A[i] - 2 * k) * B[i]
        else if( product > 0 && A[i] < 0) then
               temp = (A[i] + 2 * k) * B[i]
        else if (product > 0 && A[i] > 0)
               temp = (A[i] - 2 * k)  * B[i]
    iii. diff =  abs(product - temp)
    iV. if( diff > maxDiff )
         maxDiff = diff
     V. minimumSum = minimumSum + product

3. minimumSum = minimumSum - maxDiff

Mail us your TCS CodeVita question at vikash@programminggeek.in




         

TCS CodeVita Season IV Round1 Question: Base Camp

No comments :
Problem : Base Camp

Three friends set out to explore a remote area. They choose a safe place and make it their Base Camp. To speed up exploration time they decide to work independently. At any given point, either one or more of them can set out to explore the area. They set a protocol that after exploring the area they must meet back at the Base Camp in the evening and exchange notes.

The remote area consists of accessible and inaccessible pieces of land. Being ordinary humans, they must walk only the accessible piece of land. In order to maximize their exploration time, each one is interested in knowing about a shortest path back to the base camp.

Given that the area under exploration is arranged in form of a rectangular grid, help the explorers to chalk out a shortest path back to the base camp. Properties of a rectangle can be used as heuristic in computing distance between their positions and the Base Camp. Your task is to find out and mark the shortest path for each explorer and print each path as a separate grid.

The input and output specification sections describe how inputs will be provided on console and how output is expected back on console.
Input Format:
  1. First line of input contains grid dimensions delimited by space character
  2. Next rows number of lines contain column number of characters
  3. Valid characters are {s, d, w, -}, where
    1. s represents the location of the explorer
    2. d represents the location of the base camp
    3. w represents inaccessible region
    4. - represents accessible region
  4. End of input is marked by -1 character

Output Format:
  1. Number of grids in the output should be same as number of explorers i.e. 's' characters in the input grid
  2. Each output grid should be of the same dimension as the input grid
  3. Each output grid should contain path from explorer location s to base camp location d
  4. If there are more than one explorers, explorer with smallest value should be printed first in the output. Next smallest explorer location should be printed next followed by the last explorer grid.
  5. First explorer path should be marked by 'a' character, second by 'b' character and third by 'c' character
  6. The 's' character in the grid must be replaced by {a, b or c} whichever is appropriate for the given explorer
  7. The 's' character(s) in the grid must be replaced by '-' character for other explorer(s)
  8. Output grids must be separated by a blank line
  9. See example section for better understanding


Constraints:
1. It is guaranteed that there will always be exactly one shortest path for one explorer from a given location

Sample Input and Output


SNo.InputOutput
1
4 4
w - d -
w - w -
w - w w
s - - s
-1

w - d -
w a w -
w a w w
a - - -

w - d -
w b w -
w b w w
- - b b
2
4 4
s - - s
- - - -
- - - -
s - - d
-1

a - - -
- a - -
- - a -
- - - d

- - - b
- - - b
- - - b
- - - d

- - - -
- - - -
- - - -
c c c d


Explanation for sample input and output 1: 

Figure 1.

Figure 2.
                                                 

Note: - The output format shown above is for understanding purpose such that it highlights the shortest path between the explorer and the base camp. The examples in above table depicts output in text format as you will be required to provide.

Note:

Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.
Note:

Participants submitting solutions in C language should not use functions from / as these files do not exist in gcc
Note:

For C and C++, return type of main() function should be int.