Shipping Around an Island

Farmer John has decided to launch his own cruise ship line! He owns just one ship for now, but he is hoping for explosive growth. He recently acquired a map of the patch of ocean where the ship will operate. It looks like the diagram below, with height $H$ ($3 \le H \le 1000$) and width $W$ ($3 \le W \le 1000$).

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

On this map, . is water, A is a cell of the main island, and x is a cell belonging to some other island.

Farmer John has decided the ship will sail one full loop around the main island. Because of trade restrictions, however, the ship's route is not allowed to loop around any other island. For example, the route of length 50 below is not allowed, because it encloses the island marked 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 the map, determine the shortest route the cruise ship can take so that it loops all the way around the main island without looping around any other island.

Two cells are adjacent only if they sit directly next to each other vertically or horizontally (never diagonally). The main island is guaranteed to be connected, and a valid route is guaranteed to exist.

The route is allowed to pass through the same cell more than once. For example, the optimal route for the map above has length 62 and revisits three cells:

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

Because the route overlaps itself, that picture is hard to read, so here it is drawn again in two stages:

       ...................            ...................
       ...................            ....+--+...........
       .....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...
       ..+-------------+..            ...................

• Line 1: two space-separated integers, $H$ and $W$.
• Lines 2 through $H+1$: line $i+1$ contains $W$ characters describing row $i$ of the map (each character is ., x, or A).

• Line 1: the minimum length of a route the cruise ship can take.