题目大意：

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

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

 

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

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

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

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

 

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

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

 

这就转化成了最大匹配数

 

1 #include 
     
       2 #include 
      
        3  4 using namespace std; 5 const int N = 55; 6  7 char str[N][N]; 8 int n , m , xs[N][N] , ys[N][N] , idx , idy;//idx记录以行为轴的最大标号，idy则表示以列为轴的最大标号 9 int cx[N*N] , cy[N*N] , visy[N*N];10 bool g[N*N][N*N];//int是4个字节，用int会MLE，bool一个字节11 12 int dfs(int u)13 {14     for(int v = 1 ; v<=idy ; v++){15         if(g[u][v] && !visy[v]){16             visy[v] = 1;17             if(cy[v] == -1 || dfs(cy[v])){18                 cx[u] = v;19                 cy[v] = u;20                 return 1;21             }22         }23     }24     return 0;25 }26 27 int MaxMatch()28 {29     memset(cx , -1 , sizeof(cx));30     memset(cy , -1 , sizeof(cy));31     int ans = 0;32     for(int i=1 ; i<=idx ; i++){33         if(cx[i] == -1){34             memset(visy , 0 , sizeof(visy));35             ans += dfs(i);36         }37     }38     return ans;39 }40 41 int main()42 {43   //  freopen("a.in" , "r" , stdin);44     int T , cas = 0;45     scanf("%d" , &T);46     while(T--)47     {48         scanf("%d%d" , &n , &m);49         for(int i = 0 ; i