﻿ HDOJ1733：Escape——网络流分层图 - 落絮飞雁

# HDOJ1733：Escape——网络流分层图 Problem Description
Loneknight hates attending class very much. Every time he is attending class, when he feel tiresome with the class, he start planning the shortest path he can escape from the classroom. Therefore, he can escape from classroom so quickly that he is always the first one escape from the classroom after the class finishes. He is very proud of this fact.

One day, loneknight is day dreaming in class, and planning the shortest path for escaping. Suddently, an issue come into his mind, if everyone in the classroom want to escape as soon as possible just as loneknight, what will happend? As a kind man, loneknight want to plan a strategy that will let everyone escape from the classroom with minimum time consume. But after dozens of minutes of consideration, loneknight find this problem so difficult for him.

Now, as the best friend of him, please design a algorithm to solve this problem for him. Note that, at every time unit, everyone can move seperately up, down, left, right one unit, or stay in the old position. In addtion, no one can move to a wall or out of the room, the only way to escape is go through a gate. Moreover, at every time unit, a position can only contain a person, including gates. That means if in time t, a person escape thourgh gate g, no one can go into g in time t, but can go into g in t + 1. Now, it’s your job to calculate the minimum time required to escape for everyone.

Input
The input consists of several test cases. Each test case start with a line containing two number, n, m (1 < n, m <= 16), the rows and the columns of the room. Then n lines follow, each contain exact m characters, representing th type of unitin it. (. for empty place, X for human, # for wall, @ for gate). Input is end with EOF. Output You have to print the shortest time needed for everyone escape from the roomin a single line for each case. (-1 if impossible)

```#include
#include
#include

char mp;
const int inf=1<<30;

struct EDGE
{
int to,f,nxt;
}edge;

int n,m,s,t,nn;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int di[]={1,0,-1,0,0,1,0,-1,0,0};

int min(int a,int b)
{
return a=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='#';
}

{
edge[cnt].to=b;
edge[cnt].f=c;
edge[cnt].to=a;
edge[cnt].f=0;
}

void init()
{
cnt=ans=sum=0;
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
s=1,t=2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int num=(i-1)*m+j+2;
if(mp[i][j]=='X')
{
sum++;
}
}
nn=2+n*m;
}

int dfs(int x,int y)//DFS寻找增广路
{
vi[x][y]=1;
if(mp[x][y]=='@')
return 1;
for(int i=0;i<4;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(!in(xx,yy))
continue;
if(vi[xx][yy])
continue;
if(dfs(xx,yy))
return 1;
}
return 0;
}
int fine()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
memset(vi,0,sizeof(vi));
if(mp[i][j]=='X'&&!dfs(i,j))
return 1;
}
return 0;
}
int gfs(int x,int flow)
{
if(x==t)
return flow;
int temp=flow,pos=nn-1,j;
{
int y=edge[j].to;
int c=edge[j].f;
if(c>0&&dis[x]==dis[y]+1)
{
int temp_flow=gfs(y,min(temp,c));
temp-=temp_flow;
edge[j].f-=temp_flow;
edge[j^1].f+=temp_flow;
if(temp==0||dis[s]==nn)
return flow-temp;
}
if(c>0&&pos>dis[y])
pos=dis[y];
}
if(temp==flow)
{
if(!(--gap[dis[x]]))
dis[s]=nn;
else
gap[dis[x]=pos+1]++;
}
return flow-temp;
}
int sap()
{
int maxflow=0;
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
gap=nn;
while(dis[s]

```

#

### 推荐文章

HDOJ1733：Escape——网络流分层图

2015-11-17