The Way Home

Time limit1sMemory limit128 MB

Summary
Given a grid with children and homes, find the minimum total Manhattan-distance movement cost of a minimum-cost perfect matching between children and homes.
Level

Medium6 of 10

Topics
Graph, Greedy, Math
Solved
No attempts yet

Problem

A grid map contains the same number of children and homes. During each unit of time, every child may move one cell up, down, left, or right. You must pay 1 dollar for each move made by a child until that child reaches a home.

Each home can receive exactly one child. Find the minimum total cost needed to send all children to distinct homes.

In the map, . is an empty cell, H is a home, and m is a child. During movement, multiple children may occupy the same cell at the same time, and a child may pass through a home cell that is not their final assigned home.

Input

The input contains one or more test cases. The first line of each test case contains two integers N and M, the number of rows and columns of the map. The next N lines describe the map.

Both N and M are between 2 and 100, inclusive. The number of H cells equals the number of m cells, and there are at most 100 homes.

The input ends with a line containing 0 0.

Output

For each test case, output one line containing the minimum cost needed to send every child to a distinct home.

Examples1

  1. Example 1

    Input
    2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
    Expected output
    2
10
28