POJ 3057 Evacuation | 二分图匹配

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<vector>
  5 #include<queue>
  6 #define N 400
  7 using namespace std;
  8 int t,n,m,dis[N][N],vis[N],dx[5]={1,0,-1,0};
  9 int dy[5]={0,1,0,-1};
 10 int d_cnt,ans,adj[N][N],V[N],live,tot,bf[N];
 11 char mp[N][N];
 12 queue <int> qx,qy;
 13 inline int get(int x,int y) {return m*(x-1)+y;}
 14 void add(int T)
 15 {
 16     for (int i=1;i<=n;i++)
 17     for (int j=1;j<=m;j++)
 18         for (int k=1;k<=d_cnt;k++)
 19         if (mp[i][j]=='.' && dis[k][get(i,j)]<=T)
 20            adj[k][get(i,j)]=1;
 21 }
 22 void BFS(int X,int Y)
 23 {
 24     ++d_cnt;
 25     qx.push(X),qy.push(Y);
 26     memset(vis,-1,sizeof(vis));
 27     vis[get(X,Y)]=0;
 28     while (!qx.empty())
 29     {
 30     int x=qx.front(),y=qy.front();
 31     for (int i=0;i<4;i++)
 32     {
 33         int xx=x+dx[i],yy=y+dy[i];
 34         if (mp[xx][yy]=='.' && vis[get(xx,yy)]==-1)
 35         {
 36         qx.push(xx),qy.push(yy);
 37         vis[get(xx,yy)]=vis[get(x,y)]+1;
 38         dis[d_cnt][get(xx,yy)]=vis[get(xx,yy)];
 39         }
 40     }
 41     qx.pop(),qy.pop();
 42     }
 43 }
 44 int find(int x)
 45 {
 46     for (int i=1;i<=n*m;i++)
 47     {
 48     if (!V[i] && adj[x][i]==1)
 49     {
 50         V[i]=1;
 51         if (!bf[i] || find(bf[i]))
 52         {
 53         bf[i]=x;
 54         return 1;
 55         }
 56     }
 57     }
 58     return 0;
 59 }
 60 void init()
 61 {
 62     memset(dis,127,sizeof(dis));
 63     memset(adj,0,sizeof(adj));
 64     memset(bf,0,sizeof(bf));
 65     d_cnt=0;
 66     live=0;
 67     ans=0;
 68 }
 69 int main()
 70 {
 71     scanf("%d",&t);
 72     while (t--)
 73     {
 74     init();
 75     scanf("%d%d",&n,&m);
 76     for (int i=1;i<=n;i++)
 77         scanf("%s",mp[i]+1);
 78     for (int i=1;i<=n;i++)
 79         for (int j=1;j<=m;j++)
 80         if (mp[i][j]=='D')
 81             BFS(i,j);
 82         else if (mp[i][j]=='.') live++;
 83     for (int k=1;k<=150;k++)
 84     {
 85         add(k);
 86         for (int i=1;i<=d_cnt;i++)
 87         {
 88         memset(V,0,sizeof(V));
 89         if (find(i)) ans++;
 90         }
 91         if (ans==live)
 92         {
 93         printf("%d
",k);
 94         break;
 95         }
 96     }
 97     if (ans!=live)
 98         puts("impossible");
 99     }
100     return 0;
101 }