传送门

BZOJ

洛谷


Description

发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域。每个格子如果是’.’,那么表示这是一块空地;如果是’X’,那么表示这是一面墙,如果是’D’,那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本
不可能。


Input

第一行是由空格隔开的一对正整数NM3 \le N \le 20,3 \le M \le 20,以下NM列描述一个N \times M的矩阵。其中的元素可为字符’.’、’X’和’D’,且字符间无空格。

Output

只有一个整数K,表示让所有人安全撤离的最短时间,如果不可能撤离,那么输出’impossible’(不包括引号)。


Sample Input

5 5
XXXXX
X…D
XX.XX
X..XX
XXDXX

Sample Output

3


解题思路:

因为每一个时刻的每一个出口都只能出一个人,所以很容易想到按照时间来建图,然后跑二分图匹配就好了。首先BFS预处理出对于每一个出口,每个人到达它的时间是多少。然后我们枚举出口、人和时间,时间从最短距离到最大时间,对于每个时间都将出口和人之间连边,然后做二分图匹配就好了。

Code:

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30;
const int maxm=1.6e6+10;
const int inf=1061109567;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
struct node{int x,y;}a[maxm],b[maxm];
struct edge{int to,nxt;}e[maxm<<1];char s[maxn][maxn];
int n,m,tot,idx,cnt1,cnt2,head[maxm],match[maxm],vis[maxm],mp[maxn][maxn],dis[maxn][maxn][maxn][maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int get(int x,int y){return x*m+y;}
void add(int u,int v){e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot;}
bool dfs(int x){
    for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to){
        if(vis[v]==idx)continue;vis[v]=idx;
        if(!match[v]||dfs(match[v])){match[v]=x;return 1;}
    }return 0;
}
queue<node >q;
bool vs[maxn][maxn];
void bfs(int u,int v){
    memset(vs,0,sizeof(vs));
    while(!q.empty())q.pop();
    memset(dis[u][v],63,sizeof(dis[u][v]));
    dis[u][v][u][v]=0;vs[u][v]=1;q.push((node){u,v});
    while(!q.empty()){
        node x=q.front();q.pop();
        for(int i=0;i<4;i++){
            int xx=x.x+dx[i],yy=x.y+dy[i];
            if(0<=xx&&xx<n&&0<=yy&&yy<m&&mp[xx][yy]==1&&!vs[xx][yy])
                q.push((node){xx,yy}),dis[u][v][xx][yy]=dis[u][v][x.x][x.y]+1,vs[xx][yy]=1;
        }
    }
}
int main(){
    n=read();m=read();
    for(int i=0;i<n;i++){
        scanf("%s",s[i]);
        for(int j=0;j<m;j++){
            if(s[i][j]=='X')mp[i][j]=0;
            if(s[i][j]=='.')mp[i][j]=1,a[cnt1++]=(node){i,j};
            if(s[i][j]=='D')mp[i][j]=2,b[cnt2++]=(node){i,j};
        }
    }
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(mp[i][j]==2)bfs(i,j);
    for(int i=0;i<cnt2;i++)
        for(int j=0;j<cnt1;j++)
            if(dis[b[i].x][b[i].y][a[j].x][a[j].y]<inf)
                for(int k=dis[b[i].x][b[i].y][a[j].x][a[j].y];k<=n*m;k++)
                    add(k*cnt2+i,n*m*cnt2+j),add(n*m*cnt2+j,k*cnt2+i);
    int ret=0;
    for(int i=0;i<n*m*cnt2;i++){
        ++idx;if(dfs(i))ret++;
        if(ret==cnt1){write(i/cnt2);return 0;}
    }puts("impossible");
    return 0;
}
/*
4 5
XXDXX
XX.XX
X...X
XXDXX
*/