Maximum Cells Visited in a Grid

You are given a grid of size \(R \times C\) consisting of free cells denoted by . and obstacles denoted by #. Starting from the top-left cell (1,1) and moving only to the right or down, your task is to determine the maximum number of cells that can be visited while reaching the bottom-right cell (R,C). If the destination cannot be reached due to obstacles, output \(-1\).

Note: Both the starting cell and the destination must be free (i.e. .) for a valid path. The optimal path is determined by maximizing the count of visited cells.

Hint: Use dynamic programming with the recurrence:

[ dp[i][j] = \max\left{\begin{array}{l} dp[i-1][j] + 1 \ dp[i][j-1] + 1 \end{array}\right. ]

ensuring that you avoid cells with obstacles and handling the boundary conditions properly.

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. Each of the next \(R\) lines contains a string of length \(C\) representing a row of the grid. The grid contains only the characters . for free cells and # for obstacles.

outputFormat

Output a single integer to standard output (stdout). This integer represents the maximum number of cells that can be visited along a valid path from the top-left cell to the bottom-right cell. If no such path exists, output \(-1\).

3 3
...
.#.
...

5