FastPrep
Problem · Matrix

Find Maximum Distance

Learn this problem
● HardWells FargoOA

Problem 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
    Example 1 illustration

    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 ≤ 200
    • grid[i][j] = '.' if the cell is empty.

    More Wells Fargo problems

    drafts saved locally
    public int findMaximumDistance(String[] grid) {
  // write your code here
}
    grid[" S . . *", ". . * .", ". . . .", ". . . E"]
    expected2
    checking account