Drone's Journey

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).

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.