Sgu/527

摘要

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

（AC 360）

题意

给一个地图，问最少放几个炸弹可以把星号都消掉（炸弹炸掉当行当列）：

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

题解

神烦的一题。

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