//PKu 2195 回家 By Loli_con Enail : Loli_con@outlook.com
/*
题目叙述
=========
在一个网格图中，有n个人和n个房子。每一个单位时间，每个小人可以移动一个单位长度，无论水平还是竖直，到临近的点。对于每个人，每移动一步你需要花费1$，直到他移动到他的家，题目限制一个房子仅能住进一个人
你的任务是计算最小花费使得n个人都能住进不同的n个房子。
输入是一张地图，'.'表示空地，'H'表示房子，'m'表示人
你可以认为一个点是足够的大以至于可以同时站上去全部的n个人，当然，一个人也可以站在房子那个点而不进入。
=====================
输入叙述
=====================
多组测试数据。对于每组测试数据
第一行包括两个整数n和m，表示地图是n行m列的。
接下来n行每行m个字符，'.'、'H'、'm'含义如上。2<=n,m<=100，H<=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
=====================
解题报告
=====================
最小费用最大流模版题，KM算法也可解
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#define Max 5005
#define inf 1<<28
using namespace std;
struct kdq
{
int x,y;
}human[Max],house[Max];
int n,m;
int S,T;//源点，汇点
int cost[Max/][Max];//花费
int cap[Max/][Max];//容量
int dis[Max];
int path[Max];
bool visit[Max];
int q[Max*]; int spfa()//最短路
{
int i,j;
for(i=;i<=T;i++)
dis[i]=inf,path[i]=-,visit[i]=;
dis[S]=;
visit[S]=;
int num=,cnt=;
q[num++]=S;
while(num>cnt)
{
int temp=q[cnt++];
visit[temp]=;
for(i=;i<=T;i++)
{
if(cap[temp][i]&&dis[temp]+cost[temp][i]<dis[i])
{
path[i]=temp;
dis[i]=dis[temp]+cost[temp][i];
if(!visit[i])
{
q[num++]=i;
visit[i]=;
}
}
}
}
return dis[T]!=inf;
} int minCost=;
void getMaxFlow()//增广找最大流
{
int maxFlow=inf; while(spfa())
{
int pre=T;
while(path[pre]!=-)
{
maxFlow=min(maxFlow,cap[path[pre]][pre]);
pre=path[pre];
}
pre=T;
minCost+=dis[T]*maxFlow;//最小费用
while(path[pre]!=-)//更新流
{
cap[path[pre]][pre]-=maxFlow;
cap[pre][path[pre]]+=maxFlow;
//minCost+=cost[path[pre]][pre]*maxFlow;
pre=path[pre];
}
}
cout<<minCost<<endl;
return ;
} int getdis(kdq x,kdq y)//两个坐标之间的费用
{
return (abs(x.x-y.x)+abs(y.y-x.y));
}
void build_map(int numm,int numh)//建图
{
int i,j;
for(i=;i<=numm;i++)//计算房子和人之间的费用
for(j=;j<=numh;j++){
cost[i][j+numm]=getdis(human[i],house[j]);
cost[j+numm][i]=-cost[i][j+numm];//负费用用来回流
}
for(i=;i<=numm;i++)//源点到每个人的cap,cost
cap[S][i]=,cost[S][i]=;
for(i=;i<=numh;i++)//房子到汇点的cap,cost
cap[i+numm][T]=;
for(i=;i<=numm;i++)//每个人和房子之间的cap
for(j=;j<=numh;j++)
cap[i][j+numm]=;
}
int main()
{
int i,j,k,l;
char x;
while(scanf("%d%d",&n,&m),(n+m))
{
memset(cap,,sizeof(cap));
memset(cost,,sizeof(cost)); int numm=,numh=;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
cin>>x;
if(x=='m'){
human[++numm].x=i;
human[numm].y=j;
}
if(x=='H'){
house[++numh].x=i;
house[numh].y=j;
}
}
S=;
minCost=;
T=numm+numh+;//其实numm==numh。。。。
build_map(numm,numh);
getMaxFlow();
}
return ;
}