Amazon Online Assessment (OA) - Treasure Island II
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 one of the starting points (marked as 'S') 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.
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.
Output the minimum number of steps to get to the treasure.
Input
The input consists of an 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 'S' represents the starting point
Output
Return a minimum number of steps for the route
Examples
Example 1:
Input:
1matrix = [ 2 [โSโ, โOโ, โOโ, 'S', โSโ], 3 [โDโ, โOโ, โDโ, โOโ, โDโ], 4 [โOโ, โOโ, โOโ, โOโ, โXโ], 5 [โXโ, โDโ, โDโ, โOโ, โOโ], 6 [โX', โDโ, โDโ, โDโ, โOโ], 7]
Output: 3
Explanation:
You can start from (0,0), (0, 3), or (0, 4). The treasure locations are (2, 4), (3, 0), and (4, 0). Here, the shortest route is (0, 3), (1, 3), (2, 3), (2, 4).
Try it yourself
Solution
Prereq: 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(starts):
17 queue = deque(starts)
18 for r, c in starts:
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
34 return bfs([
35 (r, c)
36 for r, row in enumerate(matrix)
37 for c, v in enumerate(row)
38 if v == 'S'
39 ])
40
41if __name__ == "__main__":
42 rows = int(input())
43 matrix = [[x for x in input().split()] for _ in range(rows)]
44 result = routeStep(matrix)
45 print(result)
46
47
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.