hdu1045 Fire Net---二进制枚举子集-白红宇

hdu1045 Fire Net---二进制枚举子集

阅读量：5912 次

发布时间：2019-06-19

本文共 1964 字，大约阅读时间需要 6 分钟。

题目链接：

题目大意：

给你一幅n*n的图，再给你一些点，这些点的上下左右不能再放其他点，除非有墙（‘X’）隔着，问最多可以放多少个这样的点。

思路：

由于n不大于4，最多16个点，想到可以二进制枚举子集，然后逐个判断每个子集的可行性。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define FOR(i, a, b) for(int i = a; i < b; i++) 7 using namespace std; 8 int n, k; 9 char a[10][10];10 int dir[4][2] = {
   1,0,0,1,-1,0,0,-1};11 bool judge(int x)12 {13     char b[10][10];14     int c[20], tot = 0;15     memcpy(b, a, sizeof(a));16     for(int i = 0; i < n * n; i++)17     {18         if(x & (1 << i))19         {20             int xx = i / n;21             int yy = i % n;22             if(b[xx][yy] == 'X')return false;//剪枝，如果子集覆盖了墙，直接返回假 23             b[xx][yy] = 'a';24             c[tot++] = i;25         }26     }27     for(int i = 0; i < tot; i++)//从每个点出发 28     {29         int x = c[i] / n;30         int y = c[i] % n;31         for(int i = 0; i < 4; i++)//四个方向遍历 32         {33             int xx = x + dir[i][0];34             int yy = y + dir[i][1];35             while(xx >= 0 && xx < n && yy >= 0 && yy < n)//控制边界 36             {37                 if(b[xx][yy] == 'X')break;//碰到墙跳出循环 38                 if(b[xx][yy] == 'a')return false;//碰到另一个'a'说明有误 39                 xx += dir[i][0];//继续往这方向遍历 40                 yy += dir[i][1];41             }42         }43     }44     return true;45 }46 int f(int x)//返回子集中的size 47 {48     int tot = 0;49     for(int i = 0; i < (n * n); i++)50     {51         if(x & (1 << i))tot++;52     }53     return tot;54 }55 int main()56 {    57     while(cin >> n && n)58     {59         int ans = 0;60         for(int i = 0; i < n; i++)cin >> a[i];61         for(int i = 0; i < (1 << (n * n)); i++)62         {63             if(judge(i))ans = max(ans, f(i));//更新最优解 64         }65         cout << ans << endl;66     }67     return 0;68 }