Taco: Shortest Path in Grid

You are given a grid with R rows and C columns, represented as an $R \times C$ matrix. Each cell is either an open cell denoted by . or a wall denoted by #.

Your task is to find the length of the shortest path from the top-left corner (position (0, 0)) to the bottom-right corner (position (R-1, C-1)). You may only move one step at a time in four directions: up, down, left, or right. A valid move is one that stays within the grid bounds and moves to an open cell. Formally, you can move from cell (i, j) to cell (i', j') if and only if |i-i'| + |j-j'| = 1.

If there is no valid path, output -1.

inputFormat

The first line contains two integers R and C separated by a space (1 ≤ R, C ≤ 1000), representing the number of rows and columns of the grid respectively.

The following R lines each contain a string of length C, representing the grid. Each character is either . (an open cell) or # (a wall).

outputFormat

Output a single integer—the minimum number of moves required to reach from the top-left cell to the bottom-right cell. If no such path exists, output -1.

## sample

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

8

</p>