就是一道KM的模板题，而且建图已经非常显然了。关于KM算法：

KM算法流程：

(1)初始化可行顶标值

(2)用匈牙利算法寻找完备匹配

(3)若未找到完备匹配则修改可行顶标的值

(4)重复(2)(3)直到找到相等子图的完备匹配为止 上述内容转自：二分图匹配算法总结(phoenixinter)，更详细的讲述详见原文。

但是KM算法找的是最大权值，而本题要求的是最小权值。很多题解上都说把权值取反，然后最后再取反输出。但我总觉得这样做不舒服。其实也很简单，接上述文章的描述，先初始化X的可行顶标为X出发的所有边的权值的最小值，而松弛变量slack(yj) = min{w(xi, yj) - l(xi) - l(yj), |xi in S, yj not int T}，每次修改顶标时，将所有在S中的l(xi)加delta，所有在T中的l(yj)减小delta。此时要记得将所有的slack值加上delta（每次初始化也可以，复杂度上没差太多）。

//POJ 2195.cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>

//#define LOCAL
//#define READ_FILE
#define READ_FREAD
//#define VISUAL_STUDIO

const int MAXN = 110;
const int MAXPT = 210;

#ifdef LOCAL
#define LOCAL_TIME
//#define LOCAL_DEBUG
//#define STD_DEBUG
#endif

#ifdef LOCAL_TIME
#include<ctime>
#endif

#ifdef VISUAL_STUDIO
#pragma warning(disable: 4996)
#endif

#ifdef READ_FREAD
char fread_char;

inline void fread_init()
{
	fread_char = getchar();
}

inline int get_int()
{
	int ret = 0;
	while ((fread_char < '0') || (fread_char > '9'))
	{
		fread_char = getchar();
	}
	while ((fread_char >= '0') && (fread_char <= '9'))
	{
		ret = ret * 10 + fread_char - '0';
		fread_char = getchar();
	}
	return ret;
}

inline char get_char()
{
	char ret;
	while ((fread_char == ' ') || (fread_char == 'n'))
	{
		fread_char = getchar();
	}
	ret = fread_char;
	fread_char = getchar();
	return ret;
}
#endif

inline void read(int &a)
{
#ifdef READ_FREAD
	a = get_int();
#else
	scanf("%d", &a);
#endif
}

inline void read(char &a)
{
#ifdef READ_FREAD
	a = get_char();
#else
	scanf("%c", &a);
#endif
}

struct man_node
{
	int x, y;
};

typedef man_node house_node;

struct edge_node
{
	int to;
	int d;
	edge_node *next;
};

edge_node edge[MAXN * MAXN];
edge_node *head_edge[MAXPT];
int tot_edge;

man_node man[MAXN];
house_node house[MAXN];
int tot_man;
int tot_house;

inline void add_edge(const int u, const int v, const int d)
{
#ifdef LOCAL_DEBUG
	//printf("ADD_EDGE: M_X M_Y H_X H_Y D: %d %d %d %d %dn", man[u].x, man[u].y, house[v].x, house[v].y, d);
#endif
	edge[tot_edge].d = d;
	edge[tot_edge].to = v;
	edge[tot_edge].next = head_edge[u];
	head_edge[u] = edge + tot_edge++;
}

int n, m;
char map_pt;
int slack[MAXN], height_man[MAXN], height_house[MAXN];
int ans;
bool visit_man[MAXN], visit_house[MAXN];
int match_house[MAXN], match_d[MAXN];

inline int min(const int a, const int b)
{
	if (a == -1)
	{
		return b;
	}
	else if (b == -1)
	{
		return a;
	}
	return a < b ? a : b;
}

inline bool aug(const int u)
{
	visit_man[u] = true;
	int delta;
	for (edge_node *tmp = head_edge[u]; tmp != NULL; tmp = tmp->next)
	{
		if (!visit_house[tmp->to])
		{
			delta = tmp->d - height_man[u] - height_house[tmp->to];
			if (delta == 0)
			{
				visit_house[tmp->to] = true;
				if ((match_house[tmp->to] == -1) || (aug(match_house[tmp->to])))
				{
					match_house[tmp->to] = u;
					match_d[tmp->to] = tmp->d;
					return true;
				}
			}
			else
			{
				slack[tmp->to] = min(slack[tmp->to], delta);
			}
		}
	}
	return false;
}

inline void init_km()
{
	memset(slack, -1, sizeof(slack));
	memset(height_man, -1, sizeof(height_man));
	memset(height_house, 0, sizeof(height_house));
	memset(match_house, -1, sizeof(match_house));
	memset(match_d, 0, sizeof(match_d));
	ans = 0;
	for (int i = 0; i < tot_man; i++)
	{
		for (edge_node *tmp = head_edge[i]; tmp != NULL; tmp = tmp->next)
		{
			height_man[i] = min(height_man[i], tmp->d);
		}
	}
}

inline int km()
{
	init_km();
	for (int i = 0; i < tot_man; i++)
	{
#ifdef LOCAL_DEBUG
		printf("AUG: %dn", i);
#endif
		//memset(slack, -1, sizeof(slack));
		while (1)
		{
			memset(visit_man, false, sizeof(visit_man));
			memset(visit_house, false, sizeof(visit_house));
			if (aug(i))
			{
				break;
			}
			int delta = -1;
			for (int j = 0; j < tot_house; j++)
			{
				if (!visit_house[j])
				{
					delta = min(delta, slack[j]);
				}
			}
#ifdef LOCAL_DEBUG
			printf("DELTA: %dn", delta);
#endif
			for (int j = 0; j < tot_man; j++)
			{
				if (visit_man[j])
				{
					height_man[j] += delta;
				}
			}
			for (int j = 0; j < tot_house; j++)
			{
				if (visit_house[j])
				{
					height_house[j] -= delta;
				}
				else
				{
					slack[j] += delta;
				}
			}
		}
	}
	for (int i = 0; i < tot_house; i++)
	{
#ifdef LOCAL_DEBUG
		printf("HOUSE: %d %d MAX: %d %d D: %dn", house[i].x, house[i].y, man[match_house[i]].x, man[match_house[i]].y, match_d[i]);
#endif
		ans += match_d[i];
	}
	return ans;
}

int main()
{
#ifdef LOCAL_TIME
	long long start_time_ = clock();
#endif
#ifdef READ_FILE
	freopen("2195.in", "r", stdin);
#ifndef STD_DEBUG
	freopen("2195.out", "w", stdout);
#endif
#endif
#ifdef READ_FREAD
	fread_init();
#endif
	read(n);
	read(m);
	while (n != 0)
	{
		tot_man = tot_house = 0;
		memset(head_edge, 0, sizeof(head_edge));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				read(map_pt);
				if (map_pt == 'm')
				{
					man[tot_man].x = i;
					man[tot_man++].y = j;
				}
				else if (map_pt == 'H')
				{
					house[tot_house].x = i;
					house[tot_house++].y = j;
				}
			}
		}
		tot_edge = 0;
		for (int i = 0; i < tot_man; i++)
		{
			for (int j = 0; j < tot_house; j++)
			{
				add_edge(i, j, std::abs(man[i].x - house[j].x) + std::abs(man[i].y - house[j].y));
			}
		}
		printf("%dn", km());
		read(n);
		read(m);
	}
#ifdef LOCAL_TIME
	printf("run time: %lld msn", (clock() - start_time_) / 1000);
#endif
#ifdef READ_FILE
	fclose(stdin);
#ifndef STD_DEBUG
	fclose(stdout);
#endif
#endif
	return 0;
}