Minimum Steps in a Grid

You are given a grid with R rows and C columns. Each cell is either empty (represented by a dot .) or blocked (represented by a hash #). Your task is to determine the minimum number of steps required to move from the top-left corner (cell (0,0)) to the bottom-right corner (cell (R-1,C-1)), moving only in the four cardinal directions (up, down, left, right). You are not allowed to move out of bounds or into a blocked cell. If there is no possible path between these two cells, output -1.

The movement can be mathematically represented as follows: Given a current cell (i, j), the valid moves are to cells (i + d_r, j + d_c) where (d_r, d_c) \in \{(0,1), (1,0), (0,-1), (-1,0)\}.

This problem can be solved using a breadth-first search (BFS) algorithm to ensure that you find the shortest path in an unweighted grid.

inputFormat

The input is read from standard input (stdin). The first line contains two space-separated integers R and C representing the number of rows and columns of the grid respectively. This is followed by R lines, each containing a string of length C consisting of characters . (dot) and # (hash), representing the grid.

Example:

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

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of steps to reach the bottom-right corner. If it is impossible to reach the target cell, output -1.

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

8