Shortest Path on a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either . denoting a free cell or # denoting an obstacle. Your task is to determine the shortest path from the top-left cell (0-indexed) to the bottom-right cell using only the four cardinal directions (up, down, left, right). The path length is defined as the number of moves required to reach the destination.

If there is no valid path, output \(-1\). Use the Breadth-First Search (BFS) algorithm to efficiently compute the answer.

The distance computed is the number of steps taken. For example, in a grid of size \(2\times2\) with all free cells, the shortest path from the top-left to the bottom-right is of length 2.

inputFormat

The first line contains two integers n and m --- the number of rows and columns of the grid respectively.

Then follow n lines, each containing a string of length m composed of the characters . and #, representing the grid.

outputFormat

Output a single integer --- the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output \(-1\).

5 5
.....
.#.#.
.#.#.
.#.#.
.....

8