프로그램 명: delivery
제한시간: 1 초

철수는 자장면집 사장이다.

어느 하루, 도시에 있는 모든 집에서 자장면 주문을 한것 이다. 그는 그의 두명의 배달원들을 불러놓고 이렇게 말했다.

"지금 주문이 너무 많이 밀려있어서 최대한 빨리 배달하지 않으면 안된다. 둘이서 배 달할 곳을 적절히 나눠서 최대한 빨리 모든 집에 배달해야한다. 아니면 너네 둘은 해고다."

두 배달원이 해고되지 않게 모든 집에 배달 할때 걸리는 최소 시간을 구하는 프로그램 을 만들자.

두 배달원이 배달해야하는 도시가 NxM 지도로 주어진다. (3<=N<=30, 3<=M<=30) 도시는 #, ., S, H 로 구성되있다. 여기서 #은 갈수 없는 길, . 는 갈수 있는길, S는 중국집, 그리고 H는 배달해야할 집이다. 두 배달원들은 배달해야할 집들을 통과할수있 다.

두 배달원들은 위, 아래, 왼쪽, 오른쪽으로 밖에 움직일수없으며, 한번 움직일 때마다 1분이 걸린다. 그리고 배달할 때는 한개의 자장면밖에 못들고 가기 때문에, 한 집에 배달한 후 다른 곳에 또 배달해야 한다면 다시 중국집에 들렀다가 배달가야한다.

최대 15 개의 집이 주어진다. (입출력 예 참조)

입력

첫줄에는 정수 N, M 이 주어진다.

다음 N 줄에는 M 길이의 문자열이주어진다. 각 문자열은 #,.,S,H 로 구성 되있다.

출력

두 배달원들이 배달해야할곳들을 적절히 나눴을때 걸리는 최소 시간. (마지막 집에 들 렀을때 걸린 시간)

입출력 예

입력

7 8
#.S..##.
.#H.....
.#..#..#
.#.H..##
#..#....
..#.H...
########

출력

7

hint

배달원 1 이 (1,2) 와 (3,3) 에 위치한 집을 맏고, 배달원 2 가 (5,4) 를 맡으면 7 분안에 모든 집에 배달할수있다.
출처+채점데이터:likepad

[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]