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

Solution

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