Minimum Moves to Reach Grid End

You are given a grid with n rows and m columns. Each cell in the grid is either a free cell represented by a dot (.) or an obstacle represented by a hash (#). Natasha starts at the top-left cell (0, 0) and the goal is to reach the bottom-right cell (n-1, m-1) with the minimum number of moves. She is only allowed to move either right or down at each step.

If the start or end cell is blocked by an obstacle or if there is no possible path, output -1. Otherwise, output the minimum number of moves required to reach the goal.

The move cost between adjacent cells is 1. Formally, let \(G\) be the grid. You are to find the minimum number of moves required to go from \(G_{0,0}\) to \(G_{n-1,m-1}\) by only moving right \((0,1)\) and down \((1,0)\).

inputFormat

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1000), representing the number of rows and columns of the grid.

The following n lines each contain a string of length m consisting of the characters '.' (free cell) and '#' (obstacle) representing the grid.

outputFormat

Output a single integer, the minimum number of moves required to reach from the top-left cell to the bottom-right cell. If it is impossible to reach the destination, output -1.

3 4
...#
..#.
#...

5