摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
Explode 'Em All ★★☆☆☆ 答案正确 100 2015-2-5 17:28:50 超时(41)

(AC 360)

题意

给一个地图,问最少放几个炸弹可以把星号都消掉(炸弹炸掉当行当列):

   ..........
   ..***..*.*
   .*.......*
   .*.......*
   .*.......*
   .....*****
   ..........
   .........*

题解

神烦的一题。

  1. 看到这么多**..的八成就是搜索题,但是2^(25*25)明显不够,至少去掉一维。
  2. 于是先搜索来枚举在哪一行放炸弹,也就是放了x个炸弹(每行放多于一个炸掉是典型的浪费),那么剩下的n-x行一定是被竖着炸掉的。
  3. 因此要使得之前选定的炸弹能够清场,剩下的**一定所在的位置不大于x竖列。这就把一维的搜索转化为判断了。
  4. 这题时限设置得很紧,需要使用位运算压位和预处理来判断情况是否符合条件[1],原本写的是迭代加深也T了,最后裸深搜过了(广搜没试过)。

代码

527.cpp代码已折叠
展开折叠内容
#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;
}


参考资料和拓展阅读

  1. http://www.cnblogs.com/jianglangcaijin/archive/2013/05/03/3058493.html

著作权声明[编辑]

关于[编辑]