Google | Onsite | Shortest and Safest Path in Grid
Anonymous User
1153

Given a forest represented m-by-n grid. You are in grid[sx][sy] and want to reach grid[tx][ty].

Constrains:
(1) Some cells contain lions grid[i][j]=1
(2) Other cells are empty grid[i][j]=0
(3) Lion kills if we visit cell with lion. The farther from the lion you are, the safer you are.
Find the shortest and safest path from grid[sx][sy] to grid[tx][ty] by travelling farthest from lion cells.
Also tell the minimum ever distance between you and a lion in that path.

(I thought about Binary Search for safest distance from lion)

Comments (8)