시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 27 8 6 50.000%

문제

격자로 된 지도에 n명의 어린이와 n개의 집이 있다. 각각의 단위 시간동안, 모든 어린이가 한 단위만큼 움직일 수 있다. (수평이나 수직의 인접한 점으로) 당신은 각각의 어린이가 집에 들어갈 때까지, 1번 움직일 때마다 1달러의 여행비를 지불해야한다. 각각의 집에는 오직 한 명의 어린이만 들어갈 수 있다. 

당신의 목표는 n명의 어린이들을 n개의 다른 집으로 보내는데 지불해야하는 비용을 최소화 하는 것이다. 입력은 지도인데, '.' 은 빈 공간을 의미하고 'H'는 집을 의미하고 'm' 은 어린이를 의미한다.

격자로 된 지도에서 각각의 점을 격자라고 간주한다. 그리고 이 격자에 n명의 어린이를 동시에 놓을 수 있다. 또한, 한 어린이가 집으로 들어가지 않고 집의 격자로 움직이는 것은 가능하다.

입력

입력으로 하나에서 여러 개의 테스트 케이스가 있다. 각각의 케이스의 첫 줄은 N과 M의 두개의 정수이다. N은 지도의 행(row)의 개수이고, M은 지도의 열(column)의 개수이다. 입력의 나머지는 N개의 줄 지도를 묘사한다. N와 M은 둘다 2~30 사이로 가정한다. 지도에서 'H'와 'm'의 개수는 같다. 그리고 최대 100개의 집이 있을 수 있다.  N과 M 을 0 0 으로 입력하면 입력이 종료된다.

출력

각각의 테스트 케이스에서 출력의 첫 줄은 하나의 정수이다. 그것은 지불해야할 최소한의 달러의 양이다.

예제 입력

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

예제 출력

2
10
28

힌트