POJ 3057 Evacuation

POJ 3057 Evacuation

題目概述:

給一個X*Y的地圖。'X'代表不能走，'.’代表可以走且上面有一個人，'#'代表牆壁，’D’代表門。周圍只會有牆壁或門，且牆壁跟門只會在周圍。每一個門一秒只能逃出一人。請問所有人逃出至少要花幾秒。若無法逃出則輸出 "impossible"。

思路:

看了腦書的題解才會寫QQ

把每一個門分成每一個時間點來想，也就是我們去決定某一個門的某一秒要是誰走出去。

將每一個門的每一秒看作是一個節點，第i個門第k秒的點編號設為( k*(門總數) + i )。

假設r點走道d門最短路只要走t秒，我們就將r連到( (t)*(門總數) + i ),( (t+1)*(門總數) + i )......，接著再從編號1開始不斷地做匈牙利演算法，直到發現最大匹配數達到總人數時，就可以得知最少時間為(i-1)/ds + 1 (i為點編號)。

我WA了很多次因為在BFS判斷時，應該要為mp[nx][ny]=='.'，不能是其他像是mp[nx][ny]!=='X'之類的QQ

像這樣的例子就會爛掉，答案應為6。

5 5

#####

#..X#

#X..D

#..XD

#####

AC code:

//By SCJ

#include<iostream>

#include<vector>

#include<cstring>

#include<queue>

using namespace std;

#define endl '\n'

#define maxp 5000

int n,m,dis[15][15],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

char mp[15][15];

struct P{

   int x,y;

   P(int _x,int _y){x=_x;y=_y;}

};

vector<P> p,d;

vector<int>G[maxp];//door->people

int match[maxp];

bool get[150],used[150];

void init()

{

   d.clear();p.clear();

   d.push_back(P(-1,-1));

   p.push_back(P(-1,-1));

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

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

           cin>>mp[i][j];

           if(mp[i][j]=='D') d.push_back(P(i,j));

           else if(mp[i][j]=='.') p.push_back(P(i,j));

       }

   }

}

void bfs()

{

   memset(get,0,sizeof(get));

   for(int i=0;i<maxp;++i) G[i].clear();

   for(int i=1;i<d.size();++i)

   {

       memset(dis,-1,sizeof(dis));

       queue<P> Q;Q.push(d[i]);dis[d[i].x][d[i].y]=0;

       while(Q.size())

       {

           P t=Q.front();Q.pop();

           for(int k=0;k<4;++k)

           {

               int nx=t.x+dx[k],ny=t.y+dy[k];

               if(dis[nx][ny]<0&&nx<=n&&nx>=1&&ny<=m&&ny>=1&&mp[nx][ny]=='.')

               {

                   dis[nx][ny]=dis[t.x][t.y]+1;

                   Q.push(P(nx,ny));

               }

           }

       }

       for(int j=1;j<p.size();++j)

       {

           int t=dis[p[j].x][p[j].y];

           if(t<0) continue;

           get[j]=1;

           for(int k=t-1;k<=p.size();++k)

           {

               int tp=k*(d.size()-1)+i;

               G[tp].push_back(j);

           }

       }

   }

}

bool dfs(int u)

{

   for(int i=0;i<G[u].size();++i)

   {

       int v=G[u][i];

       if(used[v]) continue;

       used[v]=1;

       if(match[v]<0||dfs(match[v]))

       {

           match[v]=u;

           return true;

       }

   }

   return false;

}

void solve()

{

   if(p.size()==1)

   {

       puts("0");

       return ;

   }

   for(int i=1;i<p.size();++i)

   {

       if(get[i]==0)

       {

           puts("impossible");

           return ;

       }

   }

   memset(match,-1,sizeof(match));

   int ans=0;

   for(int i=1;i<=(p.size()-1)*(d.size()-1);++i)

   {

       memset(used,0,sizeof(used));

       if(dfs(i)) ans++;

       if(ans==p.size()-1)

       {

           int ds=d.size()-1;

           printf("%d\n",(i-1)/ds + 1);

           return ;

       }

   }

}

int main()

{

   int T;scanf("%d",&T);

   while(T--)

   {

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

       scanf("\n");

       init();

       bfs();

       solve();

   }

}