Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 代码有点长，但是感觉思路还行，1A，贴下留念~~~

Posted by yangzefeng at 2012-12-03 21:47:12 on Problem 2195
```#include<iostream>
#include<queue>

using namespace std;

#define MAX 101
#define INF (1 << 31 - 1)

struct TM
{
int x;
int y;
};
struct TH
{
int x;
int y;
};
struct TNode
{
int x;
int y;
int step;
};
TM tms[MAX];
TH ths[MAX];
int map[MAX][MAX];
int rows, cols;
int cntM, cntH;
int xx[4] = {0, 1, 0, -1};
int yy[4] = {-1, 0, 1, 0};
bool vis[MAX][MAX];
queue<TNode> qq;

void vInput()
{
int i, j;
char ch;

cntM = 0, cntH = 0;
for(i = 1; i <= rows; i++)
{
getchar();
for(j = 1; j <= cols; j++)
{
scanf("%c", &ch);
if(ch == 'm')
{
tms[++cntM].x = i;
tms[cntM].y = j;
}
else if(ch == 'H')
{
ths[++cntH].x = i;
ths[cntH].y = j;
}
}
}
}

bool inmap(int x, int y)
{
if(x > 0 && x <= rows && y > 0 && y <= cols)
return true;
return false;
}

int bfs(int start, int end)
{
int i, nx, ny;
TNode cur, temp;

cur.x = tms[start].x;
cur.y = tms[start].y;
cur.step = 0;

memset(vis, false, sizeof(vis));
while(!qq.empty())
qq.pop();

qq.push(cur);
vis[cur.x][cur.y] = true;
while(!qq.empty())
{
cur = qq.front();
qq.pop();

if(cur.x == ths[end].x && cur.y == ths[end].y)
return cur.step;

for(i = 0; i < 4; i++)
{
nx = cur.x + xx[i];
ny = cur.y + yy[i];
if(!vis[nx][ny] && inmap(nx, ny))
{
temp.x = nx;
temp.y = ny;
temp.step = cur.step + 1;
qq.push(temp);
vis[nx][ny] = true;
}
}
}

return -1;
}

void vBuiltMap()
{
int i, j;

for(i = 1; i <= cntM; i++)
for(j = 1; j <= cntH; j++)
{
map[i][j] = bfs(i, j);
}
}

int lx[MAX], ly[MAX];
bool markx[MAX], marky[MAX];

bool bHungarian(int u)
{
int v;

markx[u] = true;

for(v = 1; v <= cntH; v++)
{
if(!marky[v] && lx[u] + ly[v] == map[u][v])
{
marky[v] = true;
{
return true;
}
}
}
return false;
}

int nKM(bool isMAX)
{
int i, j, k, dd, sum;

memset(ly, 0, sizeof(ly));//初始化为0

if(!isMAX)
{
for(i = 1; i <= cntM; i++)
for(j = 1; j <= cntH; j++)
map[i][j] *= -1;
}

for(i = 1; i <= cntM; i++)
{
lx[i] = -INF;
for(j = 1; j <= cntH; j++)
{
if(lx[i] < map[i][j])
lx[i] = map[i][j];
}
}

for(i = 1; i <= cntM; i++)
{
while(1)
{
memset(markx, false, sizeof(markx));
memset(marky, false, sizeof(marky));

if(bHungarian(i))
break;

dd = INF;
for(j = 1; j <= cntM; j++)
{
if(markx[j])
{
for(k = 1; k <= cntH; k++)
{
if(!marky[k])
if(dd > (lx[j] + ly[k] - map[j][k]))
dd = lx[j] + ly[k] - map[j][k];
}
}
}

for(j = 1; j <= cntM; j++)
{
if(markx[j])
lx[j] -= dd;
if(marky[j])
ly[j] += dd;
}
}
}

sum = 0;
for(i = 1; i <= cntH; i++)
{
}

return -sum;
}

void vOut(int nOut)
{
printf("%d\n", nOut);
}

int main()
{
int nAns;

while(2 == scanf("%d%d", &rows, &cols))
{
if(rows == 0 && cols == 0)
break;
vInput();
vBuiltMap();
nAns = nKM(false);
vOut(nAns);
}
return 0;
}```

Followed by: