[poj] 3057 Evacuation

原题

题目大意

墙壁“X”，空区域（都是人）“.”，门“D”。

人向门移动通过时视为逃脱，门每秒能出去一个人，人可以上下左右移动，墙阻止移动。

求最优移动方案下，最后一个人逃脱的最短时间。如果有人无法安全逃脱（比如被墙围困住），则输出“impossible”。

解析

对于每个时间进行网络流（二分图匹配人和门）直到匹配到的人数等于总人数的时候输出，最大时间是n*m，大于即为impossible

#include<cstdio>

#include<queue>

#include<cstring>

#define pos(x,y) (x-1)*m+y

using namespace std;

int n,m,T,cnt,dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1},dis[50][150],lover[150],person,door,vis[15][15],p,QWQ;

bool v[150],mp[50][150],b;

char s[15][15];

queue <int> qx,qy,t;

void init()

{

    door=person=0;

    cnt=0;

    p=b=0;

    memset(dis,0,sizeof(dis));

    memset(vis,0,sizeof(vis));

    memset(lover,0,sizeof(lover));

}

void bfs(int x,int y)

{

    ++door;

    int rx,ry,tt;

    qx.push(x);

    qy.push(y);

    t.push(0);

    vis[x][y]=cnt;

    while (!qx.empty())

    {

	rx=qx.front();ry=qy.front();tt=t.front();

	qx.pop();qy.pop();t.pop();

	for (int i=1;i<=4;i++)

	{

	    if (s[rx+dx[i]][ry+dy[i]]=='.' && vis[rx+dx[i]][ry+dy[i]]!=cnt)

	    {

		vis[rx+dx[i]][ry+dy[i]]=cnt;

		qx.push(rx+dx[i]);qy.push(ry+dy[i]);t.push(tt+1);

		dis[door][pos(rx+dx[i],ry+dy[i])]=tt+1;

	    }

	}

    }

}

void getmap(int t)

{

    for (int i=1;i<=n;i++)

	for (int j=1;j<=m;j++)

	    for (int k=1;k<=door;k++)

		if (dis[k][pos(i,j)] && dis[k][pos(i,j)]<=t && s[i][j]=='.')

		    mp[k][pos(i,j)]=1;

		else mp[k][pos(i,j)]=0;

}

bool find(int x)

{

    for (int i=1;i<=n*m;i++)

    {

	if (!v[i] && mp[x][i])

	{

	    v[i]=1;

	    if (!lover[i] || find(lover[i]))

	    {

		lover[i]=x;

		return 1;

	    }

	}

    }

    return 0;

}

int main()

{

    scanf("%d",&QWQ);

    while (QWQ--)

    {

	scanf("%d%d",&n,&m);

	init();

	for (int i=1;i<=n;i++)

	    scanf("%s",s[i]+1);

	for (int i=1;i<=n;i++)

	    for (int j=1;j<=m;j++)

		if (s[i][j]=='D') ++cnt,bfs(i,j);

		else if (s[i][j]=='.') ++person;

	for (int i=1;i<=n*m;i++)

	{

	    getmap(i);

	    for (int j=1;j<=door;j++)

	    {

		memset(v,0,sizeof(v));

		if (find(j)) p++;

	    }

	    if (p==person)

	    {

		printf("%d\n",i);

		b=1;

		break;

	    }

	}

	if (!b) printf("impossible\n");

    }

    return 0;

}

巴特西

[poj] 3057 Evacuation

原题

题目大意

解析

最新文章

热门文章