Treasure Hunt 2

Interview

Time limit1sMemory limit512 MB

Summary

Find the minimum fuel for a ship to reach the treasure on a grid, where moves to the three cells in the next column are free and all other moves cost 1.

Level: Medium4 of 10
Topics: Graph, Shortest path, BFS, Matrix
Solved: No attempts yet

Problem

Geondeok succeeded in finding a treasure in the previous treasure hunt. Now he sails around the world as a member of a treasure expedition team.

Geondeok obtained a map of $W$ columns and $H$ rows showing the terrain of nearby islands. The map shows the surrounding sea, which is made of water and reefs. A ship cannot pass over reefs. The top-left cell of the map is $(1, 1)$ , and the bottom-right cell is $(H, W)$ .

At each step, the ship moves to one of the 8 adjacent cells. The cells adjacent to $(r, c)$ are the $(x, y)$ where $\max(|r-x|, |c-y|) = 1$ . For a safe voyage, the ship never leaves the map.

A current flows quickly from left to right across the sea on the map. Riding the current costs no fuel, but every other move costs 1 unit of fuel per cell. For example, if the ship is at $(r, c)$ , it can move to $(r-1, c+1)$ , $(r, c+1)$ , or $(r+1, c+1)$ without spending fuel. Moving to any other cell costs 1 fuel.

Input

The first line contains the height $H$ and the width $W$ of the treasure map. ( $3 \le H, W \le 500$ )

The next $H$ lines contain the map. Each character is one of .#*K, meaning sea, reef, treasure, and ship. The ship and the treasure each appear exactly once.

Output

Print the minimum amount of fuel needed to reach the treasure while pushing through the current. If the treasure cannot be reached, print $-1$ .

Examples3

Example 1
Input
```
3 5
....*
K.#..
#...#
```
Expected output
```
0
```
Example 2
Input
```
3 5
....K
*.#..
#...#
```
Expected output
```
4
```
Example 3
Input
```
3 3
K..
###
*..
```
Expected output
```
-1
```