Robot Path: Minimum Moves on a Grid

Given a grid of size (R \times C), where each cell is either free (denoted by '.') or blocked (denoted by '#'), a robot starts at the top-left corner (cell ((0,0))) and needs to reach the bottom-right corner (cell ((R-1, C-1))). In one move, the robot may move one cell up, down, left, or right. The goal is to compute the minimum number of moves required to reach the destination.

If either the starting or the destination cell is blocked, or if there is no valid path, output -1.

The movement can be interpreted as exploring a grid with obstacles. Mathematically, if we denote a blocked cell by (grid[i][j] = '#') and a free cell by (grid[i][j] = '.'), then the problem is to find the shortest path from ((0,0)) to ((R-1,C-1)) where the transitions are only allowed to adjacent free cells.

inputFormat

The input is read from standard input (stdin).

The first line contains two integers (R) and (C) ((1 \le R, C \le 1000)), separated by a space.

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

outputFormat

Output a single integer to standard output (stdout) on a single line: the minimum number of moves required to reach the bottom-right cell from the top-left cell. If the destination is unreachable, output -1.## sample

3 3
...
.#.
...

4