Robotic Vacuum Cleaner Moves

You are given a grid of size \(n \times m\) where each cell is either accessible or blocked. An accessible cell is marked with a dot (.), and a blocked cell is marked with a hash (#). A robotic vacuum cleaner starts at an accessible cell and must clean (i.e. visit) every accessible cell in the grid.

Your task is to determine the minimum number of moves required for the vacuum cleaner to cover all accessible cells. In one move, the robot may travel one cell up, down, left, or right (if the destination cell is accessible). The moves required is defined as the maximum distance from the starting cell to any other accessible cell, minimized over all choices of starting accessible cells, provided that the grid is fully connected among accessible areas. If there exists any accessible cell that cannot be reached from some starting point then the cleaning task is impossible and you should output \(-1\).

Note: The connectivity condition should hold, i.e. starting from any accessible cell, all accessible cells must be reachable. Otherwise, output \(-1\).

inputFormat

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

n m
row_1
row_2
... 
row_n

Here, \(n\) and \(m\) are integers representing the number of rows and columns of the grid, respectively. Each of the following \(n\) lines contains a string of length \(m\) made up of characters . and #, indicating accessible and blocked cells respectively.

outputFormat

Print a single integer to standard output: the minimum number of moves required to clean all accessible cells, or \(-1\) if it is impossible.

3 3
...
.#.
...

4