1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//将两个点集匹配到一起
#pragma GCC optimize(3,"Ofast","inline")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int p,h;//左边点，右边点
const int N=200;
const int INF=999999999;
int a[N][3];//左边点坐标x,y;
int b[N][3];//右边点坐标x,y;
int w[N][N];//俩点距离
int match[N];//右点匹配了那个左点
int lx[N],ly[N];//左顶点，右顶点
bool visx[N],visy[N];//左右点是否在交替路
bool find(int u)//左边点
{
	visx[u]=1;//u在交替路中
	for(int i=1;i<=h;i++)//遍历右边点
	{   //相等子图
		if(!visy[i]&&lx[u]+ly[i]==w[u][i])
		{
			visy[i]=1;//i在交替路中
			if(match[i]==-1||find(match[i]))
			{
				match[i]=u;
				return 1;
			}
		}
	}
	return 0;
}
/*
最优匹配是建立在完美匹配的基础上的，如果不存在完美匹配，那么本算法
失效(但是，我们可以人为连一些权值0的边,甚至加点，使得没有匹配的节点们最后都有
一个"虚假"的匹配)
KM求二分图最大权匹配
如果求最小权匹配
那么初始化边W为-W，
最后最大权就是最小权
*/
int km()
{	for(int i=1;i<=h;i++) match[i]=-1;
	for(int i=1;i<=p;i++)//左点初始化负无穷
		lx[i]=-INF;
	for(int i=1;i<=h;i++)//右点0
		ly[i]=0;
	for(int i=1;i<=p;i++)
	for(int j=1;j<=h;j++)
	//左点初始化最值
	lx[i]=max(lx[i],w[i][j]);
	for(int i=1;i<=p;i++)
	{
		while(1)
		{	
			for(int i=1;i<=p;i++) visx[i]=false;
			for(int i=1;i<=h;i++) visy[i]=false;
			if(find(i))break;
			int d=INF;
			for(int j=1;j<=p;j++)
				if(visx[j])//左边在交替路
				for(int k=1;k<=h;k++)
				if(!visy[k])d=min(d,lx[j]+ly[k]-w[j][k]);
			if(d==INF) return -1;//不能匹配	
			for(int j=1;j<=p;j++)if(visx[j])lx[j]-=d;
			for(int j=1;j<=h;j++)if(visy[j])ly[j]+=d;
		}
	}
	int ans=0;
	for(int i=1;i<=h;i++)ans+=w[match[i]][i];
	return -ans;
}
signed main()
{
	ios::sync_with_stdio(false); 
	cin.tie(0);cout.tie(0);
 	int n,m;
	while(cin>>n>>m)
	{//n*m的方格,m是人,每个人分配到不同的房子，走的最少距离
		p=0,h=0;
		if(n==0&&m==0)break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				char op;cin>>op;
				if(op=='m')a[++p][0]=i,a[p][1]=j;
				else if(op=='H')b[++h][0]=i,b[h][1]=j;
			}
		for(int i=1;i<=p;i++)//人
		for(int j=1;j<=h;j++)//房子
		w[i][j]=-(abs(a[i][0]-b[j][0])+abs(a[i][1]-b[j][1]));
		cout<<km()<<'\n';
	}
	return 0;
 
}