Find Maximum Distance
Learn this problem
Wells FargoOAProblem statement
The city of Hackerland can be represented as a two-dimensional grid of size n x m. Each cell is either empty (a dot character .), has an obstacle (an asterisk *), an S, or an E that represent the start and end points respectively.
One can move in four directions: up, down, left, and right. The goal is to move from the starting point to the ending point such that in the path, the minimum distance from any obstacle is as large as possible. Return this minimum possible distance.
The distance between any two points on the grid with coordinates (r1, c1) and (r2, c2) is calculated as |r1 - r2| + |c1 - c2|, where |a| is the absolute value of integer a.
Notes:
- One can visit a cell with an obstacle if necessary, i.e. no other path exists.
- A cell can be visited only once.
Function
findMaximumDistance(grid: String[]) → int
Complete the function findMaximumDistance in the editor below.
findMaximumDistance has the following parameter:
String grid[n]: An array of strings that represent the rows of the grid.
Returns
int: the largest possible minimum distance from an obstacle in any path from the starting point to the ending point
Examples
Example 1
grid = [" S . . *", ". . * .", ". . . .", ". . . E"]return = 2
Consider the following grid of size 4*4:
S . . *
. . * .
. . . .
. . . E
The optimal path is shown in the 'Cell' column. Coordinates of any of the nearest obstacles is in 'Obstacle'.
Return 2, the closest distance to any obstacle along the path.
Constraints
2 ≤ n, m ≤ 200grid[i][j]='.'if the cell is empty.