题目描述

输入格式

There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.

输出格式

For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.

题目大意

回家

题目描述

在网格地图上有 $n$ 个人和 $n$ 个房子。在每个单位时间里，每个人都可以在相邻的点上水平或垂直移动一个单位步。对于每个人，你需要为他每走一步支付 $1$ 美元的旅行费，直到他进入一所房子。由于每栋房子只能容纳一个人，这项任务很复杂。
你的任务是计算你需要支付的最低金额，以便将这 $n$ 个人送到那 $n$ 个不同的房子里。输入是场景的地图，. 表示空白空间，H表示该点上的房子，m表示在该点上有一个人。
你可以把网格地图上的每个点想象成一个相当大的正方形，所以它可以同时容纳 $n$ 个人物；此外，如果一个人在没有进入房子的情况下踩在有房子的网格上，也没关系。

输入格式

输入中有一个或多个测试用例。每种情况都以一行给出两个整数 $N$ 和 $M$ 开始，其中 $N$ 是映射的行数，$M$ 是列数。其余的输入将是描述地图的 $N$ 行。你可以假设 $N$ 和 $M$ 都在 $2$ 到 $100$ 之间，包括 $2$ 和 $100$。将有相同数量的 $H$ 和 $m$ 在地图上；最多有 $100$ 栋房子。$N$ 和 $M$ 的输入将以0 0终止。

输出格式

对于每个测试用例，输出一行带有单个整数的代码，这是您需要支付的最小金额（美元）。

翻译提供者：csyc5586

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

2
10
28