Longest Path in a Grid

You are given a grid with (R) rows and (C) columns. Each cell is either open (denoted by '.') or blocked (denoted by '#'). Your task is to compute the longest path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (R-1,C-1)) if one exists, moving only to the right or down. The length of a path is defined as the number of moves taken. If there is no valid path, output (-1).

inputFormat

The input is read from standard input (stdin) and consists of multiple lines. The first line contains two space-separated integers (R) and (C) (the number of rows and columns respectively). The following (R) lines each contain a string of length (C) composed of the characters '.' and '#' representing the grid.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of moves needed to reach the bottom-right corner if a valid path exists, otherwise output (-1).## sample

3 3
...
.#.
...

4