TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1588
  • Problem
  • P1588回家
    Limits : Time Limit : 2000 MS   Memory Limit : 65536 KB
    Description

    在一个方格构成的地图上,有k个人和k座房子。在每个单位时间,每个人只能移动一步,要么沿水平方向、要么沿垂直方向移动到相邻的格子。每个人,每移动一步需要花费1块钱,直到他进入了某个房子。每座房子只能容纳一个人。

    你的任务是计算出这k个人住进图中的k所房子所需的最小总花费。

    对于每组输入的数据,"."表示空地,"H"表示房子,"m"表示人。


    你可以认为地图上每个格子都很大,可以同时站满n个人。同时,人走到了有房子的格子后,可以选择不进该房子。

    Input Format

    有多组测试数据,对于每组数据:
    第一行是两个空格间隔的整数N和M,表示这组数据的地图由N行M列构成。
    接下来的N行M列内容就是用来描述地图的。(2<=N,M<=100)
    每组数据中房子的数量和人的数量是相同的,并且房子数不会超过100。

    如果出现了0 0,表示输入结束。

    Output Format

    对于每组测试数据,输出一行,一个整数,表示需要花费的最少费用。

    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

    Hint

    何某翻译


    Source  Pacific Northwest 2004