1. 题目

传送门=￣ω￣=

2. 题解

abs 大佬太强啦！这题打了 170 行。。。蒟蒻的 3 倍啊 Orz
此题最小费用最大流模板题，也许能用二分图的最大权匹配做。
abs 的题解：https://www.mina.moe/?p=1440

代码：

#include <bits/stdc++.h>
using namespace std;
struct edge{int u,v,c,f;}e[30005];
int n,m,c1,c2,mh[105],mw[105],hh[105],hw[105],ecnt,pre[205],dis[205],ans;
char mp[105][105];
bool book[205];
queue<int> que;
struct graph
{
    int head[205],nxt[30005],to[30005],size;
    graph(){memset(head,-1,sizeof(head)),size=0;}
    void push(int a,int b){to[size]=b,nxt[size]=head[a],head[a]=size++;}
}g;
void push(int a,int b,int c)
{
    g.push(a,ecnt),e[ecnt].u=a,e[ecnt].v=b,e[ecnt].c=c,e[ecnt++].f=1;
    g.push(b,ecnt),e[ecnt].u=b,e[ecnt].v=a,e[ecnt].c=-c,e[ecnt++].f=0;
}
bool work(int s,int t)
{
    memset(dis,127,sizeof(dis)),que.push(s),dis[s]=0,book[s]=1;
    while(!que.empty())
    {
        int f=que.front();que.pop(),book[f]=0;
        for(int i=g.head[f];i!=-1;i=g.nxt[i])
            if(e[g.to[i]].f&&dis[f]+e[g.to[i]].c<dis[e[g.to[i]].v])
            {
                dis[e[g.to[i]].v]=dis[f]+e[g.to[i]].c,pre[e[g.to[i]].v]=g.to[i];
                if(!book[e[g.to[i]].v])que.push(e[g.to[i]].v),book[e[g.to[i]].v]=1;
            }
    }
    if(dis[t]>1e8)return 0;
    for(int u=t;u!=s;u=e[pre[u]].u)
        e[pre[u]].f--,e[pre[u]^1].f++,ans+=e[pre[u]].c;
    return 1;
}
int main()
{
    while(scanf("%d%d",&n,&m),n||m)
    {
        c1=c2=ecnt=ans=g.size=0,memset(g.head,-1,sizeof(g.head));
        for(int i=0;i<n;i++)scanf("%s",mp[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(mp[i][j]=='m')mh[++c1]=i,mw[c1]=j;
                else if(mp[i][j]=='H')hh[++c2]=i,hw[c2]=j;
        for(int i=1;i<=c1;i++)
            for(int j=1;j<=c2;j++)
                push(i,j+c1,abs(mh[i]-hh[j])+abs(mw[i]-hw[j]));
        for(int i=1;i<=c1;i++)push(0,i,0);
        for(int i=1;i<=c2;i++)push(i+c1,c1+c2+1,0);
        while(work(0,c1+c2+1));
        printf("%d\n",ans);
    }
    return 0;
}