axuhongbo的个人博客

题目大意： 

给一个n∗mn∗m的矩阵， ∗∗表示石头， ..表示空地， 你可以在ijij位置放炸弹， ii行和jj列的的石头都会被炸掉， 问你最少放多少个炸弹可以把所有的石头都炸掉。

数据范围： 

1⩽n,m⩽251⩽n,m⩽25 

解题思路： 

刚开始看这道题都会想到完美匹配， 结果发现做不了， 后来想到了dfs搜索， 但是复杂度始终优化不下来， 比赛结束之后看了学长的代码才发现状压的神奇。 

对于每一行我们都可以把这一行压缩成一个数， 这个数转化成二进制之后1就代表有石头。 比如： 

..∗...∗. 

转化成： 

00100010, 对应的十进制就是2, 所以每一行我们都知道一个状态。 

那么我们可以dfs，两种状态， 当前行要么放， 要么不放。 

对于每一行的状态， 如果不放雷， 最终结果就（|）或一下当前行状态。 最后看一下最终状态里有几个1就是还有几列需要炸弹， 和行数放的雷数取个maxmax就好了。 

那么如何快速的求出最终状态有几个1呢， 可以用lowbit预处理出来。

code1:

1. #include <cstdio>

2. #include <cstring>

3. #include <iostream>

4. #include <algorithm>

5. #include <vector>

6. #include <queue>

7. #include <set>

8. #include <map>

9. #include <string>

10. #include <cmath>

11. #include <cstdlib>

12. #include <ctime>

13. #include <stack>

14. using namespace std;

15. typedef pair<int, int> PII;

16. typedef long long LL;

17. typedef unsigned long long ULL;

18. const int MaxN = 4e7;

19. char a[30][30];

20. int boom[30], f[MaxN + 5];

21. int n, m, ans;

23. void dfs(int dis, int cnt, int p){

24.     if(dis > n){

25.         int tmp = f[p];

26.         ans = min(ans, max(cnt, tmp));

27.         return;

28.     }

29.     dfs(dis + 1, cnt, p | boom[dis]); 

30.     dfs(dis + 1, cnt + 1, p);

31. }

33. int main()

34. {

35.     //freopen("input.txt", "r", stdin);

36.     //freopen("output.txt", "w", stdout);

37.     for(int i = 1; i <= (1 << 25); i++) f[i] = f[i ^ (i & (-i))] + 1;

38.     while(~scanf("%d %d", &n, &m)){

39.         ans = n * m;

40.         for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);

41.         for(int i = 1; i <= n; i++){

42.             int sum = 0, x = 1;

43.             for(int j = m; j >= 1; j--){

44.                 if(a[i][j] == '*') sum += x;

45.                 x *= 2;

46.             }

47.             boom[i] = sum;

48.         }

49.         dfs(1, 0, 0);

50.         printf("%d\n", ans);

51.     }

53.     return 0;

54. }

code2:

1. #include<bits/stdc++.h>

2. using namespace std;

3. char s[30][30];

4. int row[30], dp[(1<<25)+100];

5. int has[(1<<25)+100];

6. int lowbit(int x)

7. {

8.     return x&(-x);

9. }

10. int cal(int x)

11. {

12.     int cnt = 0;

13.     while(x)

14.     {

15.         x -= lowbit(x);

16.         cnt++;

17.     }

18.     return cnt;

19. }

20. int main()

21. {

22.     freopen("input.txt", "r", stdin);

23.     freopen("output.txt", "w", stdout);

24.     int n, m;

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

26.     for(int i = 0; i < n; i++)

27.     {

28.         has[(1<<i)] = i;

29.     }

30.     memset(row, 0, sizeof(row));

31.     for(int i = 0; i < n; i++)

32.     {

33.         scanf("%s", s[i]);

34.         for(int j = 0; j < m; j++)

35.         {

36.             if(s[i][j] == '*')

37.                 row[i] = row[i] | (1<<j);

38.         }

39.     }

40.     memset(dp, 0, sizeof(dp));

41.     int ans = 0x3f3f3f3f;

42.     int rowcnt, cowcnt;

43.     for(int i = 1; i < (1<<n); i++)

44.     {

45.         dp[i] = dp[i - lowbit(i)] | row[has[lowbit(i)]];

46.         rowcnt = n - cal(i);

47.         cowcnt = cal(dp[i]);

48.         ans = min(ans, max(rowcnt, cowcnt));

49.     }

50.     printf("%d\n", ans);

51.     return 0;

52. }

https://blog.csdn.net/ZZZZone/article/details/76992938

https://blog.csdn.net/bbbbswbq/article/details/79997713