...H....

...H....

...H....

问所有H移动到所有m上花费最少的步数

以所有H 到 所有m 连一条边，边的权重为2者距离，这样其实就是一个二分图带权匹配 也可以用KM算法来做

网络流做法类似二分图最大流做法，左右来个超级源，超级汇，然后求一边费用流即可

/*

1.WA  关于二分图匹配的数据范围要注意是否要乘以2 切记

*/

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <string>

#include <queue>

#define oo 0x13131313

using namespace std;

const int MAXN=400;

const int MAXM=200000;

const int INF=0x3f3f3f3f;

struct Edge

{

    int to,next,cap,flow,cost;

    void get(int a,int b,int c,int d)

    {

        to=a,cap=b,cost=c;next=d;flow=0;

    }

}edge[MAXM];

int head[MAXN],tol;

int pre[MAXN],dis[MAXN];

bool vis[MAXN];

int N;

void init(int n)

{

    N=n;

    tol=0;

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

}

void addedge(int u,int v,int cap,int cost)

{

    edge[tol].get(v,cap,cost,head[u]);head[u]=tol++;

    edge[tol].get(u,0,-cost,head[v]);head[v]=tol++;

}

bool spfa(int s,int t)

{

    queue<int>q;

    for(int i=0;i<N;i++)

    {

        dis[i]=INF;

        vis[i]=false;

        pre[i]=-1;

    }

    dis[s]=0;

    vis[s]=true;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=false;

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

        {

            int v=edge[i].to;

            if(edge[i].cap>edge[i].flow&&

               dis[v]>dis[u]+edge[i].cost )

            {

                dis[v]=dis[u]+edge[i].cost;

                pre[v]=i;

                if(!vis[v])

                {

                    vis[v]=true;

                    q.push(v);

                }

            }

        }

    }

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

    else return true;

}

int minCostMaxflow(int s,int t,int &cost)

{

    int flow=0;

    cost = 0;

    while(spfa(s,t))

    {

        int Min=INF;

        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])

        {

            if(Min >edge[i].cap-edge[i].flow)

              Min=edge[i].cap-edge[i].flow;

        }

        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])

        {

            edge[i].flow+=Min;

            edge[i^1].flow-=Min;

            cost+=edge[i].cost*Min;

        }

        flow+=Min;

    }

    return flow;

}

struct Home

{

    int x,y;

}H[MAXN],P[MAXN];

int totH,totP;

int NN,MM;

void input()

{

    char c;

    totH=0;totP=0;

    for(int i=1;i<=NN;i++)

   {

       for(int j=1;j<=MM;j++)

    {

        scanf("%c",&c);

        if(c=='H') totH++,H[totH].x=i,H[totH].y=j;

            else if(c=='m') totP++,P[totP].x=i,P[totP].y=j;

    }

      getchar();

   }

}

void CreatGraph()

{

    int ANS=0;

    int NNN=totP+totH;

    for(int i=1;i<=totP;i++)

      for(int j=1;j<=totH;j++)

    {

        int t=abs(P[i].x-H[j].x)+abs(P[i].y-H[j].y);

        addedge(i,j+totP,1,t);

    }

    for(int i=1;i<=totP;i++)

    addedge(NNN+1,i,1,0);

    for(int i=totP+1;i<=NNN;i++)

    addedge(i,NNN+2,1,0);

    minCostMaxflow(NNN+1,NNN+2,ANS);

    printf("%d\n",ANS);

}

void File()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

}

int main()

{

    //File();

    while(cin>>NN>>MM&&NN&&MM)

    {

        getchar();

        init(MAXN);

        input();

        CreatGraph();

    }

    return 0;

}