Interview Question
- 0of 0 votes
AnswerKingKong, the largest living ape, escaped from Xanadu lab into a forest. The forest is filled with dangerous animals, which will attack and kill human beings that venture too close to them. You are required to help the scientists find a way to get to KingKong safely. The table below gives the minimum distance one must keep from each species for safety.
- dev May 22, 2012 in United States
Animal Name
Code
Safety distance (unit cell)
Lion L 1
Panther P 2
Both, the animals as well as the scientists can move only in horizontal or vertical directions. So, in the figure, the cells shaded gray are the cells into which the scientists must NOT venture, in order to be safe. The arrow shows that the panther is one vertical and one horizontal (a total of two) cell away from it.
A snapshot of the forest is obtained from a satellite picture in terms of an MxN matrix, which is the input to your program. This snapshot gives the location of various animals in the forest. Some cells might contain trees, which merely block the path of the scientists. The cells within the snapshot are marked by:
Animal code indicating the animal present in the cell
'T' in case of a tree present in the cell
'S', which indicates the start position of the scientists
'K', KingKong's location
'#', All other cells, which are empty
The output of your program should be the number of steps in the path that the scientists should take.
Notes:
There will be a unique path, if one exists.
The entire path including the starting position of the scientist as well as KingKong's location must be safe.
Input specification:
The first line contains two integers M and N the number of rows and columns. The next M lines contain N characters from the set {'L', 'P', 'T', 'S', 'K', '#'} as explained above
Output specification:
An integer specifying the length of the path, from the starting position of the scientist, to KingKong's position both inclusive. If KingKong is not reachable safely, then output the integer '-1'.
Sample Input and Output:
Input:
7 6
TLT#PP
LL####
LL#K##
TT##TT
TT#TTT
T###TT
TTTSTT
Output:
7
Input:
11 9
LL#######
L##TTTTT#
LKTTTTTT#
####P#TT#
###PP#TT#
####P#TT#
######TT#
L##T##T##
T##T####S
T####T###
TTTTTTLL#
Output:
-1| Report Duplicate | Flag | PURGE
Java
Hmm, couldn't you just do a BFS from each dangerous animal to mark all dangerous squares as unreachable, and then just do a BFS from the scientists' position to see if there's a path of reachable squares to KK?
- eugene.yarovoi May 24, 2012