Amazon Online Assessment (OA) - Move The Obstacle

You are in charge of preparing a recently purchased lot for the Company's building.

The lot is covered with trenches and has a single obstacle that needs to be taken down before the foundation is prepared for the building.

The demolition robot must remove the obstacle before the progress can be made on the building.

Assumptions

  • The lot is flat, except the trenches, and can be represented by a 2D grid.
  • The demolition robot must start at the top left corner of the lot, which is always flat, and can move on the block up, down, right, left
  • The demolition robot cannot enter trenches and cannot leave the lot.
  • The flat areas are indicated by 1, areas with trenches are indicated by 0, and the obstacle is indicated by 9

Input

The input consists of three arguments:

numRows: an integer represents the number of rows

numColumns: an integer represents the number of columns

lot: a 2d grid of integers

Output

Return an integer that indicated the minimum distance traversed to remove the obstacle else return -1

Constraints

1<= numRows

numColumns <= 1000

Examples

Example 1:

Input:

numRows = 3
numColumns = 3
lot = [
  [1, 0, 0],
  [1, 0, 9],
  [1, 9, 1]

Output: 3

Explanation

Starting from the top-left corner, the demolition robot traversed the cells (0,0) -> (1,0)-> (2,0)->(2,1)

The robot moves 3 times to remove the obstacle 9

Try it yourself

  • preview_end: ""

Solution

#!/usr/bin/env python3

from collections import deque
from typing import List


def move_the_obstable(lot: List[List[int]]) -> int:
    '''
    >>> move_the_obstable([
    ...     [1, 0, 0],
    ...     [1, 0, 0],
    ...     [1, 9, 1],
    ... ])
    3
    '''
    num_rows = len(lot)
    num_cols = len(lot[0])

    def get_neighbors(coord):
        row, col = coord
        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            r = row + dx
            c = col + dy
            if 0 <= r < num_rows and 0 <= c < num_cols:
                yield (r, c)

    def bfs(start):
        queue = deque([start])
        r, c = start
        lot[r][c] = 0
        dist = 0
        while len(queue) > 0:
            dist += 1
            n = len(queue)
            for _ in range(n):
                node = queue.popleft()
                for r, c in get_neighbors(node):
                    if lot[r][c] == 9:
                        return dist
                    if lot[r][c] == 0:
                        continue
                    queue.append((r, c))
                    lot[r][c] = 0

    return bfs((0, 0))


if __name__ == '__main__':
    import doctest
    doctest.testmod()