TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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