Minimum Moves to Reach Destination

In a grid-based warehouse, a robot must navigate from the starting position 'S' to the destination 'D' while avoiding obstacles represented by '#' characters. The grid is defined by (N) rows and (M) columns. In one move, the robot can go up, down, left, or right. Your task is to determine the minimum number of moves required to reach the destination. If reaching the destination is impossible, output -1.

The mathematical formulation is: [ \text{answer} = \min{\text{number of moves}} ] subject to valid moves within the grid.

inputFormat

Input is given from standard input (stdin). The first line contains two integers (N) and (M) separated by a space, indicating the number of rows and columns respectively. The following (N) lines each contain a string of length (M) which represents the grid. The grid contains the characters:

• 'S' – the starting point
• 'D' – the destination
• '#' – an obstacle
• '.' – a free space

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of moves required for the robot to reach the destination. If the destination cannot be reached, output -1.## sample

5 5
S....
.##..
..#..
....#
....D

8