查看Sgu/527的源代码 ←Sgu/527

[[分类:深度优先搜索‎]][[分类:广度优先搜索‎]][[分类:位运算‎]]
==摘要==
{{信息题|Explode 'Em All|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}527|2|100|超时|41|time=2015-2-5 17:28:50}}
（AC 360）
==题意==
给一个地图，问最少放几个炸弹可以把星号都消掉（炸弹炸掉当行当列）：
    ..........
    ..***..*.*
    .*.......*
    .*.......*
    .*.......*
    .....*****
    ..........
    .........*
==题解==
神烦的一题。
#看到这么多**..的八成就是搜索题，但是<m>2^{25*25}</m>明显不够，至少去掉一维。
#于是先搜索来枚举在哪一行放炸弹，也就是放了x个炸弹<small>（每行放多于一个炸掉是典型的浪费）</small>，那么剩下的n-x行一定是被竖着炸掉的。
#因此要使得之前选定的炸弹能够清场，剩下的**一定所在的位置不大于x竖列。这就把一维的搜索转化为判断了。
#这题时限设置得很紧，需要使用位运算压位和预处理来判断情况是否符合条件<ref>http://www.cnblogs.com/jianglangcaijin/archive/2013/05/03/3058493.html</ref>，原本写的是迭代加深也T了，最后裸深搜过了（广搜没试过）。

==代码==
{{折叠|527.cpp代码已折叠
|<pre>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define ci const int &
int n,m,deep=1<<30;
int a[30]={},Count[1<<25]={};
void dfs(ci _at,ci _r,ci _count)
{
    //到达条件//
    if(_at>n)
    {
        if(Count[_r]<=_count)
            deep=min(deep,_count);
        return;
    }
    //继续搜索
    dfs(_at+1,_r|a[_at],_count);
    dfs(_at+1,_r,_count+1);
}
int main()
{
    scanf("%d %d\n",&n,&m);
    //预处理：Count[i]表示二进制数i中1的个数//
    for(int i=0;i<(1<<m);++i)
        Count[i]=Count[i>>1]+(i&1);
    //录入//
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<m ;++j )
        {
            char c;
            scanf("%c",&c);
            if(c=='*')
                a[i]|=1<<j;
        }
        getchar();
    }
    //深搜//
    dfs(1,0,0);
    printf("%d",deep);
    return 0;
}
</pre>
|sgu527}}

==参考资料和拓展阅读==
<references/>