Maximizing Distinct Cells on a Grid Path

You are given a grid with R rows and C columns. Each cell of the grid is either free (represented by '.') or an obstacle (represented by '#'). Miro starts at the cell at the top left (position (1, 1)) and must reach the cell at the bottom right (position (R, C)). He is only allowed to move either down or right at any step.

The goal is to determine the maximum number of distinct cells visited along any valid path from the start to the destination. Note that even if a cell is visited more than once, it is only counted once. If there is no valid path because either the starting cell, the ending cell, or the route between them is blocked, output -1.

The maximum number of distinct cells visited, if a path exists, can be mathematically expressed as:

provided that a valid path exists.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers R and C separated by a space.
• The next R lines each contain a string of length C consisting of the characters '.' and '#' representing the grid.

outputFormat

Print a single integer to stdout denoting the maximum number of distinct cells Miro can visit on his path. If no valid path exists, print -1.

3 3
...
...
...

5