Drone's Journey

Hard

0/120

0 upvote

Asked in company

Problem statement

You are tasked with programming a delivery drone to navigate an N x M grid. The grid contains different types of cells:

'S': The drone's starting position.

'P': The package pickup location.

'D': The delivery destination.

'.': Empty space, free to travel through.

'#': An obstacle, which cannot be entered.

The drone must complete a journey in two parts:

First, it must travel from its start 'S' to the pickup location 'P'.

Then, it must travel from the pickup location 'P' to the delivery destination 'D'.

The drone's movement capabilities change after it picks up the package:

Without the package (S to P): The drone can move one step at a time to any adjacent cell (up, down, left, or right).

With the package (P to D): The drone is heavier and can only move down or right.

Your task is to find the minimum total number of steps required for the entire journey (S -> P -> D).

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

Input Format:

The first line of input contains two space-separated integers, 'N' and 'M', the dimensions of the grid.

The next 'N' lines each contain a string of 'M' characters, representing the grid.

Output Format:

Print a single integer representing the minimum total number of steps for the full journey.

If either part of the journey is impossible (e.g., 'P' is unreachable from 'S', or 'D' is unreachable from 'P'), print -1.

Note:

The problem can be solved by running two separate Breadth-First Search (BFS) traversals: one for the S->P leg with 4-directional movement, and a second for the P->D leg with 2-directional movement.

The grid is 0-indexed.

Sample Input 1:

3 3
S.P
...
..D

Sample Output 1:

Explanation for Sample 1:

- Path from S(0,0) to P(0,2): The shortest path is `right -> right`, which takes 2 steps.
- Path from P(0,2) to D(2,2): The shortest path is `down -> down`, which takes 2 steps.
- Total minimum steps = 2 + 2 = 4.

Sample Input 2:

3 3
S.P
###
..D

Sample Output 2:

-1

Explanation for Sample 2:

 The path from S to P is possible (2 steps). However, after picking up the package at P, the drone's path to D is completely blocked by obstacles. Since the second leg of the journey is impossible, the entire journey is impossible.

Expected Time Complexity:

The expected time complexity is O(N * M).

Constraints:

1 <= N, M <= 1000
The grid will contain exactly one 'S', one 'P', and one 'D'.

Time limit: 1 sec

Approaches (1)

Approach 1

Drone's Journey

Time Complexity

Space Complexity

(100% EXP penalty)

Drone's Journey

Console