FastPrepFastPrep
Problem Brief

Avoiding the Obstacles (IMC Sydney 🦪)

INTERNOA

In this game, a player begins on a two-dimensional grid of size n × m. One cell of the grid is marked as the end and the player wants to reach this cell by moving up, down, left or right. However, some cells are occupied by obstacles. The goal of the player is to reach the end cell using a path that maximizes the minimum distance from any obstacle along that path.

The distance between any two points on the grid with coordinates (x1, y1) and (x2, y2) is calculated as |x1 - x2| + |y1 - y2|, 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 on a given path.

    • Function Description

    Complete the function findBestPath in the editor below.

    findBestPath has the following parameters:

    1. int n: the number of rows in the grid
    2. int m: the number of columns in the grid
    3. int startRow: the row index of the starting position
    4. int startColumn: the column index of the starting position
    5. int endRow: the row index of the ending position
    6. int endColumn: the column index of the ending position
    7. int[] obstacleRow: the row index of the ith obstacle
    8. int[] obstacleColumn: the column index of the ith obstacle

    Returns

    int: the largest possible minimum distance from an obstacle in any path from the starting point to the ending point

    1Example 1

    Input
    n = 4, m = 4, startRow = 0, startColumn = 0, endRow = 3, endColumn = 3, obstacleRow = [0, 1], obstacleColumn = [3, 2]
    Output
    2
    Explanation
    Example 1 illustration
    Consider the following grid of size 4*4 where empty cells are free, 'S' indicates the start, 'E' indicates the end and 'X' indicates an obstcle: The optimal path is shown in the 'cell' column. Note, the cell coordinates are given as (r, c) where r is the index of the row and c is the index of the column. Thus, the coordinates of any of the nearest obstacles is in 'Obstacle'. Coordinates of any of the nearest obstacles thus, the obstacles in the above example are located at (0, 3) and (1,2). Coordinates of any of the nearest obstacles is in 'Obstacle'. * The blocked cell (1, 2) is also 3 units distant. Return 2, the closest distance to any obstacle along the path.

    Constraints

    Limits and guarantees your solution can rely on.

  • 2 ≤ n, m ≤ 200
  • 0 ≤ startRow, endRow < n
  • 0 ≤ startColumn, endColumn < m
  • 0 ≤ number of obstacles = n * m - 2
  • 0 ≤ obstacleRow[i] < n
  • 0 ≤ obstacleColumn[i] < m
  • No obstacle at any start cell
  • There is exactly one end cell
  • There is at least one obstacle
    • public int findBestPath(int n, int m, int startRow, int startColumn, int endRow, int endColumn, int[] obstacleRow, int[] obstacleColumn) {
    // write your code here
}
    Input

    n

    4

    m

    4

    startRow

    0

    startColumn

    0

    endRow

    3

    endColumn

    3

    obstacleRow

    [0, 1]

    obstacleColumn

    [3, 2]

    Output

    2

    Sign in to submit your solution.