Shortest Path Through Warehouse

In this problem, you are given a rectangular grid representing a warehouse. The grid has ( M ) rows and ( N ) columns. Each cell of the grid is either an empty cell denoted by a dot ('.') or a shelf (obstacle) denoted by a hash ('#'). Your task is to determine the length of the shortest path from the top-left cell (position (0,0)) to the bottom-right cell (position (M-1, N-1)). Movement is allowed in four directions: up, down, left, and right. The length of a path is defined as the number of cells visited including the start and end cells. If there is no valid path from the start to the destination, output -1.

Note: The input grid is given in row-major order. Use Breadth-First Search (BFS) or a similar algorithm to solve this problem efficiently.

inputFormat

The input is read from standard input. The first line contains two space-separated integers ( M ) and ( N ), representing the number of rows and columns of the grid respectively. This is followed by ( M ) lines, each containing a string of length ( N ) representing a row of the warehouse grid. Each character in the row is either '.' (an empty cell) or '#' (a shelf).

outputFormat

Output a single integer to standard output: the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output -1.## sample

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

9