Minimum Steps to Reach the Target

Given an \(n \times m\) grid with characters '.' representing open cells and '#' representing obstacles, find the minimum number of steps required for a robot to travel from the top-left corner (cell \(1,1\)) to the bottom-right corner (cell \(n,m\)). The robot can move one step at a time in any of the four cardinal directions: up, down, left, or right. It can only move through open cells.

If the starting cell or the target cell is blocked, or if no valid path exists between them, output \(-1\).

Note: A valid move changes the current cell \((x, y)\) to one of \((x+1, y)\), \((x-1, y)\), \((x, y+1)\), or \((x, y-1)\) provided the new cell is within the grid and not an obstacle.

inputFormat

The input is read from standard input (stdin). The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 1000\)), representing the number of rows and columns of the grid respectively. The following \(n\) lines each contain a string of length \(m\) made up of the characters '.' and '#', which represent an open cell and an obstacle, respectively.

outputFormat

Output a single integer to standard output (stdout) — the minimum number of steps required for the robot to reach the bottom-right cell from the top-left cell. If it is impossible to reach the destination, output \(-1\).

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

8