Taco's Maze Adventure

An adventurer finds himself at the top-left corner of a grid and must reach the bottom-right corner by moving only in the four cardinal directions (up, down, left, right). Some cells of the grid are blocked (represented by a '#' character) and cannot be entered, while free cells are denoted by '.'. Your task is to determine the minimum number of moves required to reach the destination, or output \( -1 \) if it is impossible.

The adventurer can only move to an adjacent cell if it is within bounds and not blocked. Note that the starting cell and the destination cell must be free, otherwise the journey is impossible.

Important: Input is provided via standard input (stdin) and your program should print the result to standard output (stdout).

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of rows and columns of the grid, respectively.

This is followed by \( n \) lines, each containing a string of length \( m \). Each character is either . (free cell) or # (obstacle).

You can assume that \( 1 \leq n, m \leq 1000 \) and that the grid is well-formed.

outputFormat

Print a single integer: the minimum number of moves required to reach the bottom-right cell from the top-left cell. If it is not possible to reach the destination, print \( -1 \).

3 3
...
.#.
...

4