ZOJ 1654 Place the Robots

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：

在空地上放置尽可能多机器人，机器人朝上下左右4个方向发射子弹，子弹能穿过草地，但不能穿过墙，

两个机器人之间的子弹要保证互不干扰，求所能放置的机器人的最大个数

每个机器人所在的位置确定了，那么对应的横向和竖向子弹能到达的空地就全部被覆盖了

我们将横向所能连接在一块的空地区域标上同一个标号

比如o*o#o , 就可标号为10102因为1,3空地中间的草地不影响子弹的穿越

同理，我们将竖向的所能连接在一块的空地区域标上同一个标号

那么就可以建立一个横向到达竖向的二部图匹配

每次成功匹配一对，就相当于在这横竖交叉处放了一个炮台

这就转化成了最大匹配数

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int N = ;

 char str[N][N];

 int n , m , xs[N][N] , ys[N][N] , idx , idy;//idx记录以行为轴的最大标号，idy则表示以列为轴的最大标号

 int cx[N*N] , cy[N*N] , visy[N*N];

 bool g[N*N][N*N];//int是4个字节，用int会MLE，bool一个字节

 int dfs(int u)

 {

     for(int v =  ; v<=idy ; v++){

         if(g[u][v] && !visy[v]){

             visy[v] = ;

             if(cy[v] == - || dfs(cy[v])){

                 cx[u] = v;

                 cy[v] = u;

                 return ;

             }

         }

     }

     return ;

 }

 int MaxMatch()

 {

     memset(cx , - , sizeof(cx));

     memset(cy , - , sizeof(cy));

     int ans = ;

     for(int i= ; i<=idx ; i++){

         if(cx[i] == -){

             memset(visy ,  , sizeof(visy));

             ans += dfs(i);

         }

     }

     return ans;

 }

 int main()

 {

   //  freopen("a.in" , "r" , stdin);

     int T , cas = ;

     scanf("%d" , &T);

     while(T--)

     {

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

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

             scanf("%s" , str[i]);

         //给每行炮台所能触及的位置编为相同号

         int id =  , flag = ;

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

             if(flag) flag =  , id++;

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

                 if(str[i][j] == 'o')

                     xs[i][j] = id , idx = id , flag = ;

                 else if(str[i][j] == '#')

                     flag =  , id++;

             }

         }

         //给每列炮台所能触及的位置编为相同号

         id =  , flag = ;

         for(int i= ; i<m ; i++){

             if(flag) flag =  , id++;

             for(int j =  ; j < n ; j++){

                 if(str[j][i] == 'o')

                     ys[j][i] = id , idy = id , flag = ;

                 else if(str[j][i] == '#')

                     flag =  , id++;

             }

         }

         //构造二部图

         memset(g ,  , sizeof(g));

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

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

                 if(str[i][j] == 'o')

                     g[xs[i][j]][ys[i][j]] = true;

             }

         printf("Case :%d\n%d\n" , ++cas , MaxMatch());

     }

     return ;

 }