题目大意：
在空地上放置尽可能多机器人，机器人朝上下左右4个方向发射子弹，子弹能穿过草地，但不能穿过墙，
两个机器人之间的子弹要保证互不干扰，求所能放置的机器人的最大个数
每个机器人所在的位置确定了，那么对应的横向和竖向子弹能到达的空地就全部被覆盖了
我们将横向所能连接在一块的空地区域标上同一个标号
比如o*o#o , 就可标号为10102因为1,3空地中间的草地不影响子弹的穿越
同理，我们将竖向的所能连接在一块的空地区域标上同一个标号
那么就可以建立一个横向到达竖向的二部图匹配
每次成功匹配一对，就相当于在这横竖交叉处放了一个炮台
这就转化成了最大匹配数
1 #include <cstdio> 2 #include <cstring> 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<n ; i++) 50 scanf("%s" , str[i]); 51 52 //给每行炮台所能触及的位置编为相同号 53 int id = 1 , flag = 0; 54 for(int i=0 ; i<n ; i++){ 55 if(flag) flag = 0 , id++; 56 for(int j = 0 ; j < m ; j++){ 57 if(str[i][j] == 'o') 58 xs[i][j] = id , idx = id , flag = 1; 59 else if(str[i][j] == '#') 60 flag = 0 , id++; 61 } 62 } 63 64 //给每列炮台所能触及的位置编为相同号 65 id = 1 , flag = 0; 66 for(int i=0 ; i<m ; i++){ 67 if(flag) flag = 0 , id++; 68 for(int j = 0 ; j < n ; j++){ 69 if(str[j][i] == 'o') 70 ys[j][i] = id , idy = id , flag = 1; 71 else if(str[j][i] == '#') 72 flag = 0 , id++; 73 } 74 } 75 76 //构造二部图 77 memset(g , 0 , sizeof(g)); 78 for(int i = 0 ; i<n ; i++) 79 for(int j = 0 ; j<m ; j++){ 80 if(str[i][j] == 'o') 81 g[xs[i][j]][ys[i][j]] = true; 82 } 83 printf("Case :%d %d " , ++cas , MaxMatch()); 84 } 85 return 0; 86 }