#219. 「Going Home」 回家

「Going Home」 回家

在网格地图上有 n 个小人和 n 个房子,在单位时间内,每个小人都可以水平或垂直移动一个格子。

每个小人移动一步都会花费你1美金,知道他进入到一间房子里为止,每间房子只能容纳一人。

你需要计算,所有小人都进入到房子里,你所需要花费的金额最少是多少。

在输入的地图场景中,“.”表示空地,“H”表示房子,“m”表示小人。

地图足够大,并且小人在不进入房间的情况下,也可以踩在有房间的格子上。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个整数N和M,表示地图大小为N行M列。

接下来N行每行包含M个字符,表示完整的地图场景。

房屋数量与人数量相同,且不超过100个。

当输入一行为0 0时,表示输入终止。

输出格式

每组数据输出一个整数,表示最少花费。

每个结果占一行。

数据范围

2N,M1002 \le N,M \le 100

输入样例:

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

输出样例:

2
10
28

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解