Under construction

Still being built. Things may change

The Grove

Interview

Time limit1sMemory limit1024 MB

Summary
Find the fewest 8-directional steps for Bessie to walk around the grove of X cells and return to her start in an R by C grid.
Level

Medium5 of 10

Topics
BFS, Graph
Solved
No attempts yet

Problem

The pasture contains a small, contiguous grove of trees that has no 'holes' in the middle of it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She is sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally, counting each move as a single step. Just looking at it, she does not think you could pass 'through' the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take.

The pasture is a grid with R rows and C columns (1 ≤ R ≤ 50, 1 ≤ C ≤ 50). In the example below, '.' is pasture that Bessie may walk on, 'X' is the grove, '*' is Bessie's start and end position, and '+' marks one shortest path around the grove (the answer).

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

The path shown is not the only shortest path. Bessie might take a diagonal step from her start position and get a solution of similar length. She starts outside the grove, so she does not have to deal with a harbor-like pocket that would complicate finding the best path.

Input

The first line contains two space-separated integers R and C. Each of the following R lines contains C characters with no spaces between them. Line i+1 describes row i.

Output

Print a single integer on one line: the smallest number of steps needed for Bessie to circle the grove and return to her starting position.

Examples1

  1. Example 1

    Input
    6 7
.......
...X...
..XXX..
...XXX.
...X...
......*
    Expected output
    13