TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1588
  • 题目
  • P1588回家
    限制 : 时间限制 : 2000 MS   空间限制 : 65536 KB
    问题描述

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

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

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


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

    输入格式

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

    提示

    何某翻译


    来源  Pacific Northwest 2004