题目大意：有n个人和n间房子，一间房子只能容纳1个人，已知他们的坐标，且人只能往上下左右走，如果分配房子，走的距离之和最短？

Description

On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.

Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a ‘.’ means an empty space, an ‘H’ represents a house on that point, and am ‘m’ indicates there is a little man on that point.

You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.

Input

Output

Sample Input

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

Sample Output

2
10
28

解题思路

用KM算法求最优匹配：首先给人和房子编号，然后计算每个人分别到每件房子的距离，并建立一条边权为负距离的有向边。因为KM算法求的是最优匹配，即边权和最大的匹配，转成负权后取相反数即使最小的。如何计算距离呢？用公式算就可以了，因为地图上没有障碍！

KM算法：一开始所有人都没匹配，人的顶标为边权最大的边，房的顶标为0，这样最大边权等于两点的顶标和。用匈牙利算法寻找匹配的时候，只有顶标和等于边权才算“有边”，因为这样才是最有匹配，其他的不一定是最优的：如果大于边权，可能也大于其他边权，不能马上确定选哪一条；如果小于边权，可能也小于其他边权，还是不能确定哪一条边最优。如果边权不相等，那就记录需要顶标减少多少才能相等，否则记录b点访问过，看一下能不能和b匹配——b还没匹配或者pb可以换房。另外，没搜索一个人，就要记录人访问过，因为后面需要根据访问过的点来调整顶标。

KM算法中，一个一个人取匹配，匹配成功就为下一个人找匹配，如果没成功，那就调整顶标，直到所有人都匹配好了，顶标和即是答案。

代码中，人的编号是1到n，房的标号是106到105+n，编号并不重复，可以用一个数组记录他们的访问情况，也可以只用一个数组记录他们的顶标。

程序实现