Circumnavigate the Grove

Bessie is curious about how few steps it takes to circumnavigate a contiguous grove of trees on her pasture. The pasture is represented by an R x C grid, where each cell is one of the following:

• .: Open pasture that Bessie can traverse.
• X: A tree on the grove. The grove is contiguous and has no holes.
• *: Bessie’s unique starting (and ending) position. It is guaranteed that Bessie starts outside the grove.

Bessie may move to any adjacent cell in one step, including diagonals (i.e. the 8 directions), and each move counts as 1 step. Note that a tricky diagonal move will not allow her to pass through a gap in the grove.

Your task is to compute the minimum number of steps Bessie must take in order to leave her starting position, completely walk around the grove and return to her start. A valid circumnavigation is defined as a closed path whose winding number around any cell inside the grove is nonzero (in fact, it will be ±$2\pi$ in total). In other words, the grove must be completely enclosed by the path.

Note: It is guaranteed that a valid circumnavigation exists for the given grid.

For example, consider the following grid (where the + symbols shown below indicate one of the many possible shortest paths Bessie can take):

...+...
..+X+..
.+XXX+.
..+XXX+
..+X..+
...+++*

inputFormat

The first line contains two integers R and C ($1\le R\le50$, $1\le C\le50$) representing the number of rows and columns respectively.

The following R lines each contain a string of C characters representing the pasture. The characters will be ., X or * as described above.

outputFormat

Output a single integer: the minimum number of steps Bessie must take to circumnavigate the grove and return to her starting position.

sample

3 3
*..
.X.
...

6