Shortest Route in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either a free cell (denoted by '.') or an obstacle (denoted by '#'). Your task is to determine the shortest route (minimum number of moves) from the top-left corner (starting point) to the bottom-right corner (destination) of the grid.

You may move up, down, left, or right from a cell to an adjacent cell. The route cannot pass through cells that contain an obstacle. If there is no valid path from the start cell to the destination, output -1. Note: the positions are zero-indexed; that is, the top-left corner is at (0, 0) and the bottom-right corner is at (n-1, m-1).

The problem can be formally summarized as: find the shortest path in a grid where the allowed moves are given by:

$$\text{Directions} = \{ (0,1), (0,-1), (1,0), (-1,0) \} $$

If a path exists, output the number of moves required to reach the destination; otherwise, output -1.

inputFormat

The input is provided via stdin in the following format:

1. The first line contains two integers n and m, separated by a space, representing the number of rows and columns in the grid.
2. The next n lines each contain a string of length m representing a row of the grid.

outputFormat

The output is a single integer printed to stdout: the minimum number of moves to reach from the top-left corner to the bottom-right corner. If no valid route exists, output -1.## sample

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

6