#include <iostream>
#include <vector>
using namespace std;
#define abs(a) ( (a)> 0? (a): -(a) )
#define max( a, b ) ( (a)> (b)? (a): (b) )
#define min( a, b ) ( (a)< (b)? (a): (b) )
struct Point
{
int x, y;
Point(){}
Point( int a, int b ):
x(a), y(b) {}
};
int r, c, n, Mmax;
char map[110][110];
int mat[110][110];
bool vx[110], vy[110];
int lx[110], ly[110], match[110];
bool dfs( int u )
{
vx[u]= true;
for( int v= 1; v<= n; ++v )
if( !vy[v] && lx[u]+ ly[v]== mat[u][v] )
{
vy[v]= true;
int t= match[v];
match[v]= u;
if( t== -1 || dfs(t) ) return true;
match[v]= t;
}
return false;
}
void build()
{
vector<Point> man, house;
for( int i= 0; i< r; ++i )
for( int j= 0; j< c; ++j )
if( map[i][j]== 'm' ) man.push_back( Point(i,j) );
else if( map[i][j]== 'H' ) house.push_back( Point(i,j) );
memset( mat, 0, sizeof(mat) );
for( size_t i= 0; i< man.size(); ++i )
for( size_t j= 0; j< house.size(); ++j )
{
mat[i+1][j+1]= abs( man[i].x- house[j].x )+ abs( man[i].y- house[j].y );
Mmax= max( mat[i+1][j+1], Mmax );
}
n= max( man.size(), house.size() );
memset( lx, 0, sizeof(lx) );
memset( ly, 0, sizeof(ly) );
memset( vx, false, sizeof(vx) );
memset( vy, false, sizeof(vy) );
for( int i= 1; i<= n; ++i ) match[i]= -1;
Mmax++;
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
mat[i][j]= Mmax- mat[i][j];
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
lx[i]= max( lx[i], mat[i][j] );
}
int KM()
{
for( int u= 1; u<= n; ++u )
while( true )
{
memset( vx, false, sizeof(vx) );
memset( vy, false, sizeof(vy) );
if( dfs(u) ) break;
int d= 1<<30;
for( int i= 1; i<= n; ++i )
if( vx[i] )
for( int j= 1; j<= n; ++j )
if( !vy[j] )
d= min( lx[i]+ ly[j]- mat[i][j], d );
for( int i= 1; i<= n; ++i )
{
if( vx[i] ) lx[i]-= d;
if( vy[i] ) ly[i]+= d;
}
}
int result= 0;
for( int i= 1; i<= n; ++i )result+= mat[ match[i] ][i];
return result;
}
int main()
{
while( scanf("%d%d",&r,&c), r+ c )
{
getchar();
for( int i= 0; i< r; ++i ) gets( map[i] );
build();
printf("%d\n", n* Mmax- KM() );
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
#define abs(a) ( (a)> 0? (a): -(a) )
#define Min(a,b) ( (a)< (b)? (a): (b) )
#define INF 1<<30
struct Point
{
int x, y;
Point( int a= 0,int b= 0 ): x(a),y(b) {}
};
int r, c;
char graph[110][110];
vector<Point> man, house;
int map[210][210];
int cost[210][210], n;
int min_cost()
{
int ans= 0;
int pre[210], dist[210];
while( true )
{
for( int i= 0; i<= n; ++i ) dist[i]= INF;
dist[0]= 0;
while( true )
{
bool ok= false;
for( int i= 0; i< n; ++i )
for( int j= 1; j<= n; ++j )
if( map[i][j]> 0 && dist[i]+ cost[i][j]< dist[j] )
{
dist[j]= dist[i]+ cost[i][j], pre[j]= i;
ok= true;
}
if( !ok ) break;
}
if( dist[n]== INF ) break;
int min= INF, t= n;
while( t!= 0 ) min= Min( map[pre[t]][t], min ),t= pre[t];
t= n;
while( t!= 0 ) map[pre[t]][t]-= min, map[t][pre[t]]+= min,t= pre[t];
ans+= min* dist[n];
}
return ans;
}
int main()
{
while( scanf("%d%d",&r,&c), r+ c!= 0 )
{
getchar(); man.clear(), house.clear();
memset( map, 0, sizeof(map) );
memset( cost, 0, sizeof(cost) );
for( int i= 0; i< r; ++i ) gets( graph[i] );
for( int i= 0; i< r; ++i )
for( int j= 0; j< c; ++j )
if( graph[i][j]== 'H' ) house.push_back( Point(i,j) );
else if( graph[i][j]== 'm' ) man.push_back( Point(i,j) );
n= house.size()+ man.size()+ 1;
int len= man.size()+ 1;
for( int i= 1; i< len; ++i ) map[0][i]= 1;
for( int i= len; i< len+ house.size(); ++i ) map[i][n]= 1;
for( size_t i= 0; i< man.size(); ++i )
for( size_t j= 0; j< house.size(); ++j )
{
map[i+1][j+len]= 1;
cost[i+1][j+len]= abs( man[i].x- house[j].x )+ abs( man[i].y- house[j].y );
cost[j+len][i+1]= -cost[i+1][j+len];
}
printf("%d\n", min_cost() );
}
return 0;
}
posted on 2009-02-14 12:19
Darren 閱讀(321)
評(píng)論(0) 編輯 收藏 引用