1 //这是一个最小费用最大流问题

  2 //最大费用最小流只要在添加边的时候换一下位置就好了

  3 //求最大费用最大流只需要把费用换成相反数，用最小费用最大流求解即可

  4 #include <cstdio>

  5 #include <cstring>

  6 #include <algorithm>

  7 #include <queue>

  8 #include <cmath>

  9 using namespace std;

 10 const int MAXN = 10000;

 11 const int MAXM = 100000;

 12 const int INF = 0x3f3f3f3f;

 13 struct Edge

 14 {

 15     int v, next, cap, flow, cost;

 16     int x, y;

 17 } e[MAXM];

 18 struct shudui

 19 {

 20     int x,y;

 21 }p1[MAXN],p2[MAXN];

 22 int head[MAXN],tol;

 23 int pre[MAXN],dis[MAXN];

 24 bool vis[MAXN];

 25 int N, M;

 26 void init()

 27 {

 28     N = MAXN;

 29     tol = 0;

 30     memset(head, -1, sizeof(head));

 31 }

 32 void add_edge(int x,int y,int cap,int cost)

 33 {

 34     e[tol].v=y;

 35     e[tol].cap=cap;

 36     e[tol].flow=0;

 37     e[tol].cost=cost;

 38     e[tol].next=head[x];

 39     head[x]=tol++;

 40

 41     e[tol].v=x;

 42     e[tol].cap=0;

 43     e[tol].flow=0;

 44     e[tol].cost=-cost;

 45     e[tol].next=head[y];

 46     head[y]=tol++;

 47 }

 48 int spfa(int s,int t)

 49 {

 50     queue<int>r;

 51     for(int i=0;i<MAXN;++i)

 52     {

 53         vis[i]=0;

 54         dis[i]=INF;

 55         pre[i]=-1;

 56     }

 57     dis[s]=0;

 58     vis[s]=1;

 59     r.push(s);

 60     while(!r.empty())

 61     {

 62         //printf("**\n");

 63         int u=r.front();

 64         r.pop();

 65         vis[u]=0;

 66         for(int i=head[u];i!=-1;i=e[i].next)

 67         {

 68             int v=e[i].v;

 69             if(e[i].cap>e[i].flow && dis[v]>dis[u]+e[i].cost)

 70             {

 71                 dis[v]=dis[u]+e[i].cost;

 72                 pre[v]=i;

 73                 if(!vis[v])

 74                 {

 75                     vis[v]=1;

 76                     r.push(v);

 77                 }

 78             }

 79         }

 80     }

 81     if(pre[t]==-1) return 0;

 82     else return 1;

 83 }

 84 int MincostMaxflow(int s,int t,int &cost)

 85 {

 86     int flow=0;

 87     cost=0;

 88     while(spfa(s,t))

 89     {

 90

 91         int minn=INF;

 92         for(int i=pre[t];i!=-1;i=pre[e[i^1].v])

 93         {

 94             if(minn>e[i].cap-e[i].flow)

 95             {

 96                 minn=e[i].cap-e[i].flow;

 97             }

 98         }

 99         for(int i=pre[t];i!=-1;i=pre[e[i^1].v])

100         {

101             e[i].flow+=minn;

102             e[i^1].flow-=minn;

103             cost+=e[i].cost*minn;

104         }

105         flow+=minn;

106     }

107     return flow;

108 }

109

110 int main()

111 {

112     int n,m,st,en;

113     char s[105][105];

114     while(~scanf("%d%d",&n,&m) && n+m)

115     {

116         init();

117         int index1=0,index2=0;

118         for(int i=1;i<=n;++i)

119             scanf("%s",s[i]+1);

120         st=0;

121         for(int i=1;i<=n;++i)

122         {

123             for(int j=1;j<=m;++j)

124             {

125                 if(s[i][j]=='m')

126                 {

127                     index1++;

128                     p1[index1].x=i;

129                     p1[index1].y=j;

130

131                 }

132                 else if(s[i][j]=='H')

133                 {

134                     index2++;

135                     p2[index2].x=i;

136                     p2[index2].y=j;

137

138                 }

139             }

140         }

141         //printf("%d %d\n",index1,index2);

142         en=index1+index2+1;

143         for(int i=1;i<=index1;++i)

144         {

145             add_edge(st,i,1,0);

146         }

147         for(int i=index1+1;i<=index1+index2;++i)

148         {

149             add_edge(i,en,1,0);

150         }

151         for(int i=1;i<=index1;++i)

152         {

153             for(int j=1;j<=index2;++j)

154             {

155                 int cost=abs(p1[i].x-p2[j].x)+abs(p1[i].y-p2[j].y);

156                 add_edge(i,index1+j,1,cost);

157             }

158         }

159         int ans=0;

160         MincostMaxflow(st,en,ans);

161         printf("%d\n",ans);

162     }

163     return 0;

164 }