Problem Brief

Find Maximum Distance

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 Description

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

1Example 1

Input

grid = [" S . . *", ". . * .", ". . . .", ". . . E"]

Output

Explanation

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

Limits and guarantees your solution can rely on.

2 ≤ n, m ≤ 200
grid[i][j] = '.' if the cell is empty.