Longest Path in a Grid with Obstacles

In this problem, you are given an n×m grid where each cell is either free (represented by '.') or blocked (represented by '#'). Your task is to determine the length of the longest path from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)) while only moving rightwards or downwards. If either the start or destination cell is blocked, or if there is no valid path, you should return -1.

More formally, let (dp[i][j]) represent the maximum number of moves required to reach cell ( (i,j) ) from cell ( (1,1) ) using only moves to the right or moves downward. The transition is given by: [ dp[i][j] = \max{ dp[i-1][j],\ dp[i][j-1] } + 1 \quad \text{if cell } (i,j) \text{ is free} ] with the base condition (dp[1][1]=0) if the starting cell is free. If no valid path exists, the answer is -1.

Note: The indexing in the explanation is 1-based, but while implementing, you can use 0-based indexing.

inputFormat

The input is given via standard input (stdin). The first line contains two integers (n) and (m) indicating the number of rows and columns in the grid. The following (n) lines each contain a string of length (m) consisting of the characters '.' (free cell) and '#' (obstacle).

outputFormat

Output a single integer to standard output (stdout), which is the length of the longest path from the top-left corner to the bottom-right corner following the given rules. If no valid path exists, output -1.## sample

3 4
..#.
..##
...#

-1