Longest Simple Path in a Grid

Given an n x m grid consisting of characters . (representing empty cells) and # (representing obstacles), find the length of the longest simple path (without revisiting any cell) from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1, m-1)). The length is defined as the number of moves (transitions between cells). If either the starting cell or the destination cell is blocked or if there is no valid path, output -1. Note that if n = 1 and m = 1, the length is 0 because no move is needed.

The problem can be mathematically formalized as: Find the maximum integer L such that there exists a sequence of distinct cells \[ (x_0,y_0), (x_1,y_1), \ldots, (x_L,y_L) \] where \((x_0,y_0) = (0,0)\) and \((x_L,y_L) = (n-1,m-1)\), and for every consecutive pair, the cells are adjacent (sharing an edge), and each cell is visited at most once. If no such sequence exists, output \(-1\).

inputFormat

The input is read from stdin and is formatted as follows:

1. The first line contains two integers n and m (1 ≤ n, m ≤ small), representing the number of rows and columns of the grid.
2. The following n lines each contain m tokens (each token is either . or #) separated by spaces, representing the grid.

outputFormat

Print a single integer to stdout — the length of the longest path from the top-left to the bottom-right corner. If no such path exists, output -1.

3 3
. . #
. # .
. . .

4