Minimum Steps to Treasure

You are given an R x C grid representing a dungeon. Each cell is either a free cell denoted by '.' or a wall denoted by '#'. You start at the top-left corner (0,0) and need to reach the treasure located at the bottom-right corner (R-1,C-1) by moving in the four cardinal directions (up, down, left, right).

Your task is to compute the minimum number of steps required to reach the treasure. If it is impossible to reach the treasure, output -1.

The movement is only allowed on cells that are not walls. The starting and ending cell must also be free ('.').

Note: Each move from one cell to an adjacent cell counts as 1 step.

The mathematical formulation: Given a grid \(G\) with \(R\) rows and \(C\) columns, find the minimum \(d\) such that there exists a path from \((0, 0)\) to \((R-1, C-1)\) using legal moves, i.e., \[ d = \min \{ \text{number of moves from } (0,0) \text{ to } (R-1,C-1) \}\] If no such path exists, return \(-1\).

inputFormat

The input is given from standard input (stdin) and has the following format:

R C
row1
row2
...
rowR

Where the first line contains two space-separated integers \(R\) and \(C\) indicating the number of rows and columns, respectively. The following \(R\) lines each contain a string of length \(C\) representing a row of the grid.

outputFormat

Output the minimum number of steps required to reach the treasure from the starting position on a single line. If there is no valid path, output -1.

## sample

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

8