Maze Shortest Path

Given a maze represented by a grid of characters, your task is to find the minimum number of moves required to travel from the top-left corner to the bottom-right corner. The maze consists of only two types of cells: a free cell represented by a dot ('.') and a blocked cell represented by a hash ('#'). You can move up, down, left, or right and each move counts as one step. If it is impossible to reach the destination, output (-1).

The maze is provided as an (n \times m) grid. Formally, let (maze[i][j]) denote the cell in the (i)-th row and (j)-th column. The cell (maze[i][j]) is available if (maze[i][j] = '.') and blocked if (maze[i][j] = '#'). Your task is to compute the minimum number of moves from cell ((0, 0)) to ((n-1, m-1)), or return (-1) if no such path exists.

inputFormat

The first line contains two integers (n) and (m) (1 ≤ n, m ≤ 1000) indicating the number of rows and columns of the maze. The following (n) lines each contain a string of length (m) consisting only of the characters '.' and '#'. It is guaranteed that each string represents one row of the maze.

outputFormat

Output a single integer on a new line: the minimum number of moves required to go from the top-left corner to the bottom-right corner. If it is impossible to reach the destination, output (-1).## sample

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

6