Treasure Island Route

Hard

0/120

0 upvote

Asked in company

Problem statement

You are given a 2D map, represented by a matrix of characters, that marks the location of a treasure island. Some areas of the map are safe to sail, while others contain dangerous rocks and reefs. Your goal is to find the shortest possible route from your starting position to the treasure.

The map is defined as follows:

'O' represents a safe area to sail.

'D' represents a dangerous area with rocks or reefs, which you cannot enter.

'X' represents the treasure island, your destination.

You must start at the top-left corner (0, 0) of the map, which is always a safe area. From any given block, you can move one step up, down, left, or right. You cannot move into dangerous 'D' blocks or move outside the map boundaries.

Your task is to find and return the minimum number of steps required to reach the treasure island 'X'. If the treasure is unreachable, return -1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers, R and C, representing the number of rows and columns in the map.

The next R lines each contain C characters (without spaces), representing the map.

Output Format:

Print a single integer representing the minimum number of steps to reach the treasure.

If the treasure cannot be reached, print -1.

Note:

An element from array 'a' and an element from array 'b' can be part of only one pair. Once used, they cannot be used again to form another pair.

Sample Input 1:

4 4
OOOO
DODO
OOOO
XDDO

Sample Output 1:

Explanation for Sample 1:

The shortest path from the start (0, 0) to the treasure 'X' at (3, 0) is:
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 0) -> (3, 0)
This route requires a total of 5 steps.

Sample Input 2:

3 3
OXO
DDD
OXO

Sample Output 2:

-1

Explanation for Sample 2:

The treasure at (0, 1) is surrounded by dangerous 'D' blocks. It is impossible to reach it from the starting position. Therefore, the output is -1.

Expected Time Complexity:

The expected time complexity is O(R*C).

Constraints:

1 <= R, C <= 100
The map will contain only the characters 'O', 'D', and 'X'.
There will be exactly one 'X' in the map.
The top-left corner (0, 0) will always be 'O'.

Time Limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Treasure Island Route

Console