Maze Escape: Shortest Path in a Maze

You are given an m x n maze represented as a grid. Each cell in the maze is either a free path denoted by . or a wall denoted by #. Your task is to determine the minimum number of steps required to travel from the starting position at the top-left corner (0,0) to the destination at the bottom-right corner (m-1, n-1).

You are allowed to move in four cardinal directions: up, down, left, and right. If there is no valid path that leads to the destination, output -1.

Formally, if we denote the starting cell as \((0,0)\) and the ending cell as \((m-1,n-1)\), then you need to find the shortest path (in number of steps) that connects these two cells. The constraints are given by \(1 \le m, n \le 1000\).

inputFormat

The input is given via stdin with the following format:

• The first line contains two integers m and n, separated by a space, representing the number of rows and columns of the maze.
• The next m lines each contain a string of length n consisting of characters . and # that represent the maze.

outputFormat

Output a single integer on stdout which is the minimum number of steps required to reach the destination. If there is no path, output -1.

## sample

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

8

</p>