Labyrinth
By Cristhian Bonilha, UTFPR 
Brazil
By Cristhian Bonilha, UTFPR Brazil
Paper labyrinths is Rafael's favorite hobbie, but he's usually complaining that the labyrinths he finds are too easy. To be more specific, the distance between the entrance of the labyrinth and the exit is always too short.
The entrance of the labyrinth is from where the player must start to solve it, and the exit is where he must get. The player can walk in four directions – up, right, down or left – and the distance between the entrance and the exit of the labyrinth is given by the sum of steps of the shortest path.
Given a labyrinth of N lines and M columns, figure out what is the maximum distance that can be found if the entrance and exit is choosen in a optimum way.
There will be several test cases. Each test case starts with two integers N and M (5 ≤ N, M ≤ 500), representing the number of lines and columns of the labyrinth, respectively.
Following there will be N lines containing M characters each, representing the labyrinth. The character of the i-th line and the j-th column indicates what is in the position i, j. If the character is a “.” (dot), it means that such position has an empty space, where the player can pass over. If it's “#”, it means that such position is an obstacle, where the player can't pass over.
There are always at least two empty spaces in the grid, and there is only one path between any two empty spaces. The entrance and exit of the labyrinth don't necessarily need to be on the border.
The last test case is indicated when N = M = 0, which shouldn't be processed.
For each test case print one line, containing one integer, indicating the distance between the entrance and exit of the labyrinth if the position of the entrance and exit are choosen in a optimum way.
| Sample Input | Sample Output |
|
5 5 |
8 16 |