Shortest Path in a Grid

Given a grid with ( n ) rows and ( m ) columns, where each cell is either passable (denoted by '.') or impassable (denoted by '#'), your task is to compute the length of the shortest path from the top-left cell (0, 0) to the bottom-right cell (( n-1, m-1 )). You may move up, down, left, or right from a cell to an adjacent cell. If there is no valid path, output (-1).

The input is provided via standard input. The first line contains two integers ( n ) and ( m ), representing the number of rows and columns respectively. Each of the following ( n ) lines contains a string of length ( m ) representing a row of the grid.

inputFormat

The input is read from standard input (stdin).

The first line contains two space-separated integers ( n ) and ( m ) (where ( 1 \leq n, m \leq 1000 ) for instance), representing the number of rows and columns of the grid. The next ( n ) lines each contain a string of length ( m ) consisting of the characters '.' and '#' only.

outputFormat

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

4 4
....
.##.
..#.
....

6