시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB211706152.137%

문제

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

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

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

입력

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

N과 M 을 0 0 으로 입력하면 입력이 종료된다.

출력

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

예제 입력 1

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

예제 출력 1

2
10
28
W3sicHJvYmxlbV9pZCI6IjMwNzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWUzOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhY2E5XHVjNzkwXHViODVjIFx1YjQxYyBcdWM5YzBcdWIzYzRcdWM1ZDAgblx1YmE4NVx1Yzc1OCBcdWM1YjRcdWI5YjBcdWM3NzRcdWM2NDAgblx1YWMxY1x1Yzc1OCBcdWM5ZDFcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMmU4XHVjNzA0IFx1YzJkY1x1YWMwNFx1YjNkOVx1YzU0OCwgXHViYWE4XHViNGUwIFx1YzViNFx1YjliMFx1Yzc3NFx1YWMwMCBcdWQ1NWMgXHViMmU4XHVjNzA0XHViOWNjXHVkMDdjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjMjE4XHVkM2M5XHVjNzc0XHViMDk4IFx1YzIxOFx1YzljMVx1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjODEwXHVjNzNjXHViODVjKSBcdWIyZjlcdWMyZTBcdWM3NDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzViNFx1YjliMFx1Yzc3NFx1YWMwMCBcdWM5ZDFcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YjU0Y1x1YWU0Y1x1YzljMCwgMVx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3N2MgXHViNTRjXHViOWM4XHViMmU0IDFcdWIyZWNcdWI3ZWNcdWM3NTggXHVjNWVjXHVkNTg5XHViZTQ0XHViOTdjIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC4mbmJzcDtcdWFjMDFcdWFjMDFcdWM3NTggXHVjOWQxXHVjNWQwXHViMjk0IFx1YzYyNFx1YzljMSBcdWQ1NWMgXHViYTg1XHVjNzU4IFx1YzViNFx1YjliMFx1Yzc3NFx1YjljYyBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzU4IFx1YmFhOVx1ZDQ1Y1x1YjI5NCBuXHViYTg1XHVjNzU4IFx1YzViNFx1YjliMFx1Yzc3NFx1YjRlNFx1Yzc0NCBuXHVhYzFjXHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHViY2Y0XHViMGI0XHViMjk0XHViMzcwIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM5YzBcdWIzYzRcdWM3NzhcdWIzNzAsICYjMzk7LiYjMzk7IFx1Yzc0MCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCAmIzM5O0gmIzM5O1x1YjI5NCBcdWM5ZDFcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwICYjMzk7bSYjMzk7IFx1Yzc0MCBcdWM1YjRcdWI5YjBcdWM3NzRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXNlcnVwbG9hZFwvc3NpbGI0XC8yMDE2MDIxMVwvZTMwMWMyN2FhMDI3NmY2YWZlMTc4NjBlOGU2ZTBiOGUucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWNhOVx1Yzc5MFx1Yjg1YyBcdWI0MWMgXHVjOWMwXHViM2M0XHVjNWQwXHVjMTFjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTBcdWM3NDQgXHVhY2E5XHVjNzkwXHViNzdjXHVhY2UwIFx1YWMwNFx1YzhmY1x1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCBcdWFjYTlcdWM3OTBcdWM1ZDAgblx1YmE4NVx1Yzc1OCBcdWM1YjRcdWI5YjBcdWM3NzRcdWI5N2MgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1ZDU1YyBcdWM1YjRcdWI5YjBcdWM3NzRcdWFjMDAgXHVjOWQxXHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YWMwMFx1YzljMCBcdWM1NGFcdWFjZTAgXHVjOWQxXHVjNzU4IFx1YWNhOVx1Yzc5MFx1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWQ1NThcdWIwOThcdWM1ZDBcdWMxMWMgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNzQwIE5cdWFjZmMgTVx1Yzc1OCBcdWI0NTBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBOXHVjNzQwIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWQ1ODkocm93KVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAsIE1cdWM3NDAgXHVjOWMwXHViM2M0XHVjNzU4IFx1YzVmNChjb2x1bW4pXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzkwNCBcdWM5YzBcdWIzYzRcdWI5N2MgXHViYjE4XHVjMGFjXHVkNTVjXHViMmU0LiBOXHVjNjQwIE1cdWM3NDAgXHViNDU4XHViMmU0IDJ+MTAwJm5ic3A7XHVjMGFjXHVjNzc0XHViODVjIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHVjOWMwXHViM2M0XHVjNWQwXHVjMTFjICYjMzk7SCYjMzk7XHVjNjQwICYjMzk7bSYjMzk7XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWFjMTlcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzU4IFx1YzlkMVx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YWNmYyBNIFx1Yzc0NCAwIDAgXHVjNzNjXHViODVjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjODg1XHViOGNjXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YWM4M1x1Yzc0MCBcdWM5YzBcdWJkODhcdWQ1NzRcdWM1N2NcdWQ1NjAgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YjJlY1x1YjdlY1x1Yzc1OCBcdWM1OTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA3MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdvaW5nIEhvbWUiLCJkZXNjcmlwdGlvbiI6IjxwPk9uIGEgZ3JpZCBtYXAgdGhlcmUgYXJlIG4gbGl0dGxlIG1lbiBhbmQgbiBob3VzZXMuIEluIGVhY2ggdW5pdCB0aW1lLCBldmVyeSBsaXR0bGUgbWFuIGNhbiBtb3ZlIG9uZSB1bml0IHN0ZXAsIGVpdGhlciBob3Jpem9udGFsbHksIG9yIHZlcnRpY2FsbHksIHRvIGFuIGFkamFjZW50IHBvaW50LiBGb3IgZWFjaCBsaXR0bGUgbWFuLCB5b3UgbmVlZCB0byBwYXkgYSAkMSB0cmF2ZWwgZmVlIGZvciBldmVyeSBzdGVwIGhlIG1vdmVzLCB1bnRpbCBoZSBlbnRlcnMgYSBob3VzZS4gVGhlIHRhc2sgaXMgY29tcGxpY2F0ZWQgd2l0aCB0aGUgcmVzdHJpY3Rpb24gdGhhdCBlYWNoIGhvdXNlIGNhbiBhY2NvbW1vZGF0ZSBvbmx5IG9uZSBsaXR0bGUgbWFuLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gY29tcHV0ZSB0aGUgbWluaW11bSBhbW91bnQgb2YgbW9uZXkgeW91IG5lZWQgdG8gcGF5IGluIG9yZGVyIHRvIHNlbmQgdGhlc2UgbiBsaXR0bGUgbWVuIGludG8gdGhvc2UgbiBkaWZmZXJlbnQgaG91c2VzLiBUaGUgaW5wdXQgaXMgYSBtYXAgb2YgdGhlIHNjZW5hcmlvLCBhICZyc3F1bzsuJnJzcXVvOyBtZWFucyBhbiBlbXB0eSBzcGFjZSwgYW4gJnJzcXVvO0gmcnNxdW87IHJlcHJlc2VudHMgYSBob3VzZSBvbiB0aGF0IHBvaW50LCBhbmQgYW0gJmxzcXVvO20mcnNxdW87IGluZGljYXRlcyB0aGVyZSBpcyBhIGxpdHRsZSBtYW4gb24gdGhhdCBwb2ludC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZ29pbmdob21lLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwNXB4OyB3aWR0aDoyNDlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3UgY2FuIHRoaW5rIG9mIGVhY2ggcG9pbnQgb24gdGhlIGdyaWQgbWFwIGFzIGEgcXVpdGUgbGFyZ2Ugc3F1YXJlLCBzbyBpdCBjYW4gaG9sZCBuIGxpdHRsZSBtZW4gYXQgdGhlIHNhbWUgdGltZTsgYWxzbywgaXQgaXMgb2theSBpZiBhIGxpdHRsZSBtYW4gc3RlcHMgb24gYSBncmlkIHdpdGggYSBob3VzZSB3aXRob3V0IGVudGVyaW5nIHRoYXQgaG91c2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSBhcmUgb25lIG9yIG1vcmUgdGVzdCBjYXNlcyBpbiBpbnB1dC4gRWFjaCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBnaXZpbmcgdHdvIGludGVnZXJzIE4gYW5kIE0sIHdoZXJlIE4gaXMgdGhlIG51bWJlciBvZiByb3dzIG9mIHRoZSBtYXAsIGFuZCBNIGlzIHRoZSBudW1iZXIgb2YgY29sdW1ucy4gVGhlIHJlc3Qgb2YgdGhlIGlucHV0IHdpbGwgYmUgTiBsaW5lcyBkZXNjcmliaW5nIHRoZSBtYXAuIFlvdSBtYXkgYXNzdW1lIGJvdGggTiBhbmQgTSBhcmUgYmV0d2VlbiAyIGFuZCAxMDAsIGluY2x1c2l2ZS4gVGhlcmUgd2lsbCBiZSB0aGUgc2FtZSBudW1iZXIgb2YgJmxzcXVvO0gmcnNxdW87cyBhbmQgJmxzcXVvO20mcnNxdW87cyBvbiB0aGUgbWFwOyBhbmQgdGhlcmUgd2lsbCBiZSBhdCBtb3N0IDEwMCBob3VzZXMuIElucHV0IHdpbGwgdGVybWluYXRlIHdpdGggMCAwIGZvciBOIGFuZCBNLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIHdpdGggdGhlIHNpbmdsZSBpbnRlZ2VyLCB3aGljaCBpcyB0aGUgbWluaW11bSBhbW91bnQsIGluIGRvbGxhcnMsIHlvdSBuZWVkIHRvIHBheS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d