Shortest Path in Grid

Given an n × m grid composed only of two characters: . (a passable cell) and # (an obstacle), your task is to compute the length of the shortest path from the top‐left corner at \((0,0)\) to the bottom‐right corner at \((n-1, m-1)\). You may only move up, down, left, or right. If no such path exists, output \(-1\). This problem can be solved efficiently using a Breadth-First Search (BFS) algorithm.

inputFormat

The input is read from stdin and has the following format:

The first line contains two integers n and m, representing the number of rows and columns respectively. The next n lines each contain a string of length m consisting exclusively of the characters . and # indicating, respectively, a free cell or an obstacle.

outputFormat

Print a single integer to stdout that represents the length of the shortest path from \((0,0)\) to \((n-1, m-1)\). If a valid path does not exist, output \(-1\).

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

8