Treasure Island Multi Start
MediumBFS · Amazon
A map is given as grid, a list of equal-length strings. Each cell is one of:
'S'a possible starting point (there can be several)'X'a treasure (there can be several)'O'open water you can sail through'D'dangerous rocks you cannot enter
You begin on any one 'S' cell of your choice. In one move you go one cell up, down, left or right, and you may not leave the grid or enter a 'D' cell. 'S' and 'X' cells can be passed through like open water.
Return the minimum number of moves needed to reach any 'X' cell, or -1 if no treasure is reachable (including when the grid has no 'S' or no 'X').
Example 1
- Input:
- grid = ["SOOD", "DODO", "OOOX", "SDOO"]
- Output:
- 4
- Explanation
- The top start needs 5 moves (right, down, down, right, right). The bottom start at
(3, 0)goes up to(2, 0)and then right three times to the treasure at(2, 3): 4 moves. The best start wins.
Example 2
- Input:
- grid = ["SDO", "DDO", "OOX"]
- Output:
- -1
- Explanation
- The only start is boxed in by rocks on both sides, so no treasure can be reached.
Example 3
- Input:
- grid = ["XOOS", "ODDO", "OOOX"]
- Output:
- 2
- Explanation
- There are two treasures. From the start at
(0, 3)the one at(0, 0)is 3 moves away along the top row, but the one at(2, 3)is only 2 moves straight down.
Constraints
1 <= grid.length, grid[i].length <= 500- All rows have the same length
- Every cell is one of
'S','X','O','D'