23817번 - 포항항

문제

당신은 에브리타임을 둘러보다가 한 글을 보았다!

이 글을 보고 공포에 사로잡힌 당신은 주변에 과메기를 파는 식당에 달려가기로 하였다. 하지만 요즘 과메기가 인기가 많아 식당에서는 1인분씩만 팔고 있다. 따라서 당신은 총 다섯 식당을 찾아가 과메기를 먹어야 한다. 슬슬 포항항항 하며 웃음이 나오려고 한다. 최대한 빨리 과메기를 먹고 저주를 풀자!

$N \times M$ 크기의 지도가 주어진다. 지도에서 당신의 위치는 'S', 식당의 위치는 'K'로 주어진다. 또한, 지도 중간중간에 장애물이 존재하며, 장애물은 'X'로 주어진다. 당신은 지도 상에서 한 칸씩 상하좌우로 움직일 수 있고, 한 칸을 이동하는데 1분이 걸린다. 장애물이 있는 칸으로는 이동할 수 없다.

5개의 식당을 방문하는 데 필요한 최소한의 시간을 출력하자.

입력

첫째 줄에 $N, M ,円 (4 \leq N, M \leq 1,000)$이 주어진다.

그 이후 $N$개의 줄에 걸쳐 각 줄에 길이 $M$의 문자열이 주어진다.

'.'은 빈 칸, 'X'는 장애물, 'S'는 현재 위치, 'K'는 식당을 의미한다 (1ドル \leq$ 식당의 수 $\leq 20$).

출력

'S'에서 출발하여 주어진 식당 중 5개의 식당을 방문하는 데 걸리는 최소한의 시간을 출력하여라. 만약 5개의 식당을 방문할 수 없는 경우 $-1$을 출력한다.

제한

힌트

첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다.

두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수 없다.