Shortest Path in a Grid

You are given a grid with . representing open cells and # representing obstacles. Your task is to determine the length of the shortest path from the top-left corner to the bottom-right corner. You may move in four directions: up, down, left, or right. The path length is equal to the number of cells visited (including both the start and the destination).

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

Formally, if we denote the number of rows by \(R\) and the number of columns by \(C\), and the grid is given as an array of strings, you must determine the shortest sequence of moves that leads from cell (0, 0) to cell (R-1, C-1). The valid moves are shown in the diagram below:

[ \begin{array}{ccc} & \uparrow & \ \leftarrow & \text{Current} & \rightarrow \ & \downarrow & \end{array} ]

If no path exists, output -1.

inputFormat

The first line contains two integers \(R\) and \(C\) representing the number of rows and columns.

The next \(R\) lines each contain a string of length \(C\) consisting only of characters . (for open cells) and # (for obstacles).

outputFormat

Output a single integer: the length of the shortest path from the top-left cell to the bottom-right cell. If no such path exists, output \(-1\).

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

-1