Description

Farmer John decided to start his own cruise ship line! He has but one ship, but is hoping for big growth. He recently acquired a map of the area of ocean where his cruise ship will operate. It looks something like the diagram below, with height $H$ ($3 \leq H \leq 1000$) and width $W$ ($3 \leq W \leq 1000$).

................... 
................... 
.....A............. 
.....A..x.......... 
..x..A.....AAAA.... 
.....A.....A..A.... 
.....AAAAAAAA.A.... 
........A.....A.... 
.xx...AAA...x.A.... 
......A............ 
...AAAAAAAAAAAAA... 
................... 

In this map, '.' denotes water; 'A' is an element of the main island; and 'x' are other islands.

Farmer John has decided his cruise ship will loop around the main island. However, due to trade restrictions, the path his ship takes is NOT allowed to go around any other islands. For instance, the following path of length 50 is not allowed because it encloses the island denoted by 'x'.

................... 
....+--+........... 
....|A.|........... 
....|A.|x.+-----+.. 
..x.|A.+--+AAAA.|.. 
....|A.....A..A.|.. 
....|AAAAAAAA.A.|.. 
....|...A.....A.|.. 
.xx.|.AAA...x.A.|..    <--- route circumnavigates 'x' -- illegal! ..+-+.A.........|.. 
..|AAAAAAAAAAAAA|.. 
..+-------------+.. 

Given a map, help Farmer John determine the shortest path his cruise ship can take to go around the main island without going around any other islands.

Two cells are considered connected if they lie vertically or horizontally across from one another (not diagonally). It is guaranteed that the main island is connected and that a solution exists. The path may start on any water cell and may visit the same square more than once. For instance, there are three squares that are visited more than once in FJ's optimal path (of length 62) for the example:

................... 
....+--+........... 
....|A.|........... 
....|A.|x.+----+... 
..x.|A.+--+AAAA|... 
....|A.....A..A|... 
....|AAAAAAAA.A|... 
....|...A..+-+A|... 
.xx.|.AAA..|x|A|... 
..+-+.A....+-+-++.. 
..|AAAAAAAAAAAAA|.. 
..+-------------+.. 

The above diagram is somewhat unclear because of the path overlapping itself. Drawn in two stages, FJ's optimal path is:

...................            ................... 
...................            ....+--+........... 
.....A.............            ....|A.|........... 
.....A..x..........            ....|A.|x.+----+... 
..x..A.....AAAA....            ..x.|A.+--+AAAA|... 
.....A.....A..A....  and then  ....|A.....A..A|... 
.....AAAAAAAA.A....            ....|AAAAAAAA.A|... 
....V...A..+>.A....            ....V...A...>+A|... 
.xx.|.AAA..|x.A....            .xx...AAA...x|A|... 
..+-+.A....+----+..            .....A.......+-+... 
..|AAAAAAAAAAAAA|..            ...AAAAAAAAAAAAA... 
..+-------------+..            ................... 

John obtained a map of size $H$ ($3 \leq H \leq 1000$) by $W$ ($3 \leq W \leq 1000$). '.' denotes water, 'A' denotes the main island, and 'x' denotes other small islands. He wants to pilot his ship once around the main island, but the route must not circumnavigate any other islands. The path may start on any water cell, and a cell may be visited any number of times. Find the minimum length of such a route.

Input Format

• Line 1: Two space-separated integers $H$ and $W$ ($3 \leq H, W \leq 1000$).
• Lines 2..$H+1$: Each of the next $H$ lines contains $W$ characters describing a map row, each character being '.' or 'x' or 'A'.

Output Format

• Line 1: A single integer — the minimum length of a valid path that Farmer John's cruise ship can take.

12 19 
................... 
................... 
.....A............. 
.....A..x.......... 
..x..A.....AAAA.... 
.....A.....A..A.... 
.....AAAAAAAA.A.... 
........A.....A.... 
.xx...AAA...x.A.... 
......A............ 
...AAAAAAAAAAAAA... 
................... 

62 

Hint

Translated by ChatGPT 5