Shortest Path in a Grid

You are given one or more grids, where each grid is represented by an n x m matrix (2 ≤ n, m ≤ 100). Each cell in the matrix is either empty ('.') or blocked ('#'). Your task is to determine the shortest path from the top‐left corner (starting cell) to the bottom‐right corner (destination) of the grid. You can move in the four cardinal directions: up, down, left, and right. If there is no valid path from the start to the destination, output "No path".

Each dataset begins with two integers n and m, followed by n lines describing the grid. A dataset with n = m = 0 indicates the end of input. For each dataset, output the length of the shortest path. The length of the path is defined as the number of cells visited including the starting cell and the destination cell.

A useful concept for solving this problem is the Breadth-First Search (BFS) algorithm. The step count can be interpreted mathematically as follows:

[ \text{path_length} = \min_{\text{all valid paths}} { #\text{ of steps} }]

If no valid path exists, print "No path".

inputFormat

Input consists of multiple datasets. Each dataset starts with a line containing two integers n and m (2 ≤ n, m ≤ 100) representing the number of rows and columns. The next n lines each contain a string of m characters, where each character is either a dot ('.') indicating an open cell or a hash ('#') indicating a blocked cell. The end of input is signaled by a line containing "0 0". Input is provided via standard input (stdin).

outputFormat

For each dataset, output a single line containing the minimum number of steps required to travel from the top-left to the bottom-right cell. If no valid path exists, output "No path". Output should be written to standard output (stdout).## sample

2 2
.#
#.
0 0

No path