Amazon Online Assessment (OA) 2021 - Move The Obstacle | Demolition Robot | Robot Find Path

1from collections import deque
2from typing import List
3
4def move_obstacle(lot: List[List[int]]) -> int:
5    num_rows = len(lot)
6    num_cols = len(lot[0])
7
8    def get_neighbors(coord):
9        row, col = coord
10        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
11            r = row + dx
12            c = col + dy
13            if 0 <= r < num_rows and 0 <= c < num_cols:
14                yield (r, c)
15
16    def bfs(start):
17        queue = deque([start])
18        r, c = start
19        lot[r][c] = 0
20        dist = 0
21        while len(queue) > 0:
22            dist += 1
23            n = len(queue)
24            for _ in range(n):
25                node = queue.popleft()
26                for r, c in get_neighbors(node):
27                    if lot[r][c] == 9:
28                        return dist
29                    if lot[r][c] == 0:
30                        continue
31                    queue.append((r, c))
32                    lot[r][c] = 0
33
34    return bfs((0, 0))
35
36if __name__ == '__main__':
37    lot = [[int(x) for x in input().split()] for _ in range(int(input()))]
38    res = move_obstacle(lot)
39    print(res)
40