Amazon Online Assessment (OA) - Treasure Island I

You have a map that marks the location of a treasure island. Some of the map areas have jagged rocks and dangerous reefs. Other areas are safe to sail in.

There are other explorers trying to find the treasure, so you must figure out the shortest route to the treasure island.

Assume the map area is a two-dimensional grid, represented by a matrix of characters.

You must start from the top-left corner of the map and can move one block up, down, left, or right at a time.

The treasure island is marked as 'X' in a block of the matrix. 'X' will not be at the top-left corner.

Any block with dangerous rocks or reefs will be marked as 'D'. You must not enter dangerous blocks. You cannot leave the map area.

Other areas 'O' are safe to sail in. The top-left corner is always safe.

Output the minimum number of steps to get to the treasure.

Input

The input consists of one argument:

matrix: a 2D string array where X represents the treasure island, D represents dangerous rocks or reefs, O represents safe to sail in areas, and The starting point is always 'O', representing a safe area. There is no 'S' representing the starting point mentioned within the matrix description.

Output

Return the minimum number of steps for the route.

Examples

Example 1:

Input:

1matrix = [
2  ['O', 'O', 'O', 'O'],
3  ['D', 'O', 'D', 'O'],
4  ['O', 'O', 'O', 'O'],
5  ['X', 'D', 'D', 'O'],
6]

Output: 5

Explanation:

Route is (0, 0), (0, 1), (1, 1), (2, 1), (2, 0), (3, 0). The minimum route takes 5 steps.

Try it yourself

Solution

Prerequisite: Number of Islands

1from typing import List
2
3def routeStep(matrix: List[List[str]]) -> int:
4    from collections import deque
5    num_rows = len(matrix)
6    num_cols = len(matrix[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 and matrix[r][c] != 'D':
14                yield (r, c)
15
16    def bfs(start):
17        queue = deque([start])
18        r, c = start
19        matrix[r][c] = ' '
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 matrix[r][c] == 'X':
28                        return dist
29                    if matrix[r][c] == ' ':
30                        continue
31                    queue.append((r, c))
32                    matrix[r][c] = ' '
33    return bfs((0, 0))
34
35if __name__ == "__main__":
36    rows = int(input())
37    matrix = [[x for x in input().split()] for _ in range(rows)]
38    result = routeStep(matrix)
39    print(result)
40
41