Programming Geek
Rated 4.1/5 based on 446 reviews

TCS CodeVita Season IV Round1 Question: Base Camp

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.