27978번 - 보물 찾기 2

건덕이는 지난 보물찾기에서 보물을 찾는 데 성공했다. 이제는 배를 타고 세계 곳곳을 누비며 보물을 찾아 나서는 보물 탐사대가 되었다.

건덕이는 주변 섬들의 지형이 담긴 가로 $W$칸, 세로 $H$칸의 지도를 구했다. 지도에는 주변 바다의 지형이 나타나 있다. 바다와 암초로 이루어져 있는데, 배는 암초 위를 지나다닐 수 없다. 지도의 가장 왼쪽 위는 $(1, 1)$, 오른쪽 아래는 $(H, W)$이다.

건덕이의 배는 매번 인접한 8칸 중 한 곳으로 이동할 수 있다. $(r, c)$와 인접한 칸은 $\max(|r-x|, |c-y|) = 1$인 $(x, y)$ 이다. 안전한 항해를 위해 지도 바깥으로는 나가지 않는다.

바다의 물살이 지도 기준 왼쪽에서 오른쪽으로 빠르게 흐르고 있어서, 물살을 타고 가는 데에는 연료가 들지 않지만, 그 외에는 한 칸당 1의 연료가 소모된다. 예를 들어, 건덕이가 현재 $(r, c)$ 위치에 자리 잡고 있다면 $(r-1, c+1), (r, c+1), (r+1, c+1)$로는 연료 소모 없이 이동할 수 있고, 그 외의 칸으로는 $1$의 연료를 소모해야 한다.

건덕이의 손에 보물지도가 주어졌다. 보물을 찾기까지 소모해야 하는 연료의 최솟값을 구해 주자!

첫 번째 줄에 보물 지도의 세로 길이 $H$, 가로 길이 $W$가 주어진다. $(3 \le H, W \le 500)$

두 번째 줄부터 $H$개의 줄에 걸쳐 지도가 주어진다. 지도는 .#*K 중 하나로만 나타내져 있으며, 각각 바다, 암초, 보물, 배를 의미한다. 배와 보물은 지도에 한 번만 주어진다.

물살을 헤쳐 보물을 찾기까지 소모하는 연료의 최솟값을 출력한다. 도달할 수 없는 경우에는 $-1$을 출력한다.