Shortest Path in a Grid

You are given a rectangular grid containing several types of cells. Each cell is represented by a character:

• S: The starting position (exactly one in the grid).
• D: The destination position (exactly one in the grid).
• .: An empty cell where you can move.
• #: An obstacle cell that cannot be traversed.

Your task is to determine the shortest path from the starting cell S to the destination cell D. You can move in four directions: up, down, left, and right. Each move costs 1 unit.

If we denote the cost of moving as \(1\) per step, then the total cost of a path with \(k\) moves is \(k\). If no valid path exists, output \(-1\).

inputFormat

The first line of input contains two space-separated integers \(R\) and \(C\) representing the number of rows and columns in the grid, respectively.

This is followed by \(R\) lines, each containing a string of length \(C\), which represents the grid.

outputFormat

Output a single integer representing the length of the shortest path from S to D. If no such path exists, output \(-1\).

3 4
S...
.#..
.#D.

4