（以“分类:深度优先搜索分类:广度优先搜索分类:位运算 ==摘要== {{信息题|Explode 'Em All|http://acm.sgu.ru/problem.php?contest{...”为内容创建页面） |
小 （→题解：Math公式） |
||
| 第15行： | 第15行： | ||
==题解== | ==题解== | ||
神烦的一题。 | 神烦的一题。 | ||
| − | #看到这么多**..的八成就是搜索题，但是<m>2^ | + | #看到这么多**..的八成就是搜索题，但是<m>2^{25*25}</m>明显不够，至少去掉一维。 |
#于是先搜索来枚举在哪一行放炸弹，也就是放了x个炸弹<small>（每行放多于一个炸掉是典型的浪费）</small>，那么剩下的n-x行一定是被竖着炸掉的。 | #于是先搜索来枚举在哪一行放炸弹，也就是放了x个炸弹<small>（每行放多于一个炸掉是典型的浪费）</small>，那么剩下的n-x行一定是被竖着炸掉的。 | ||
#因此要使得之前选定的炸弹能够清场，剩下的**一定所在的位置不大于x竖列。这就把一维的搜索转化为判断了。 | #因此要使得之前选定的炸弹能够清场，剩下的**一定所在的位置不大于x竖列。这就把一维的搜索转化为判断了。 | ||
#这题时限设置得很紧，需要使用位运算压位和预处理来判断情况是否符合条件<ref>http://www.cnblogs.com/jianglangcaijin/archive/2013/05/03/3058493.html</ref>，原本写的是迭代加深也T了，最后裸深搜过了（广搜没试过）。 | #这题时限设置得很紧，需要使用位运算压位和预处理来判断情况是否符合条件<ref>http://www.cnblogs.com/jianglangcaijin/archive/2013/05/03/3058493.html</ref>，原本写的是迭代加深也T了，最后裸深搜过了（广搜没试过）。 | ||
| + | |||
==代码== | ==代码== | ||
{{折叠|527.cpp代码已折叠 | {{折叠|527.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| Explode 'Em All | ★★☆☆☆ | 答案正确 | 100 | 2015-2-5 17:28:50 | 超时（41） |
（AC 360）
给一个地图，问最少放几个炸弹可以把星号都消掉（炸弹炸掉当行当列）：
.......... ..***..*.* .*.......* .*.......* .*.......* .....***** .......... .........*
神烦的一题。
| 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;
}
|
CloudLunar