Drone Delivery Shortest Path

You are given an n x m grid representing a map for a drone delivery system. The grid contains three types of cells: the starting point denoted by S, the delivery point denoted by D, and obstacles denoted by #. Other cells are passable.

The drone can move in the four cardinal directions (up, down, left, right). Your task is to determine the minimum number of moves required for the drone to travel from S to D. If no valid path exists, output "No Path Found".

Mathematically, if the drone moves from a cell at coordinates \((x,y)\) to any adjacent cell, the path distance is computed as:

[ d = \sum_{i=1}^{k} 1 ]

where \(k\) is the number of moves required. Use breadth-first search (BFS) to find the shortest path.

inputFormat

The first line contains two space-separated integers n and m representing the number of rows and columns, respectively. The next n lines each contain a string of length m representing a row of the grid.

outputFormat

Output a single line. If there exists a path from S to D, print the minimum number of moves. Otherwise, print No Path Found.

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

7