在网格地图上有 n 个小人和 n 个房子,在单位时间内,每个小人都可以水平或垂直移动一个格子。
每个小人移动一步都会花费你1美金,知道他进入到一间房子里为止,每间房子只能容纳一人。
你需要计算,所有小人都进入到房子里,你所需要花费的金额最少是多少。
在输入的地图场景中,“.”表示空地,“H”表示房子,“m”表示小人。
地图足够大,并且小人在不进入房间的情况下,也可以踩在有房间的格子上。
输入包含多组测试数据。
每组测试数据第一行包含两个整数N和M,表示地图大小为N行M列。
接下来N行每行包含M个字符,表示完整的地图场景。
房屋数量与人数量相同,且不超过100个。
当输入一行为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