CloudLunar
主页
知识库
人文社科
自然科学
跨学科领域
热门分类
算法及题库
云璟月's
墨色集(设计)
指尖集(代码)
未央集(随笔)
流觞集(语录)
如花集(书影)
纸鸢集(小说)
登录
B站
微博
人人
开心
Twitter
Facebook
RSS订阅链接
留言板
关于我
在社交网站上关注我
B站
微博
人人
开心
Twitter
Facebook
RSS订阅
RSS订阅链接
留言板
关于我
查看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/>
该页面使用的模板:
模板:=
(
查看源代码
)
模板:信息题
(
查看源代码
)
模板:折叠
(
查看源代码
)
返回
Sgu/527
。
著作权声明
[
编辑
]
除非另有说明,本
网站内容
采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
进行许可(中国大陆可以参照
知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议
,如有不同以前者为准)。
如果需要商业化使用,请另联系作者取得授权。
关于
[
编辑
]
联系
@云璟月Lunar
的新浪微博
本站RSS:
RSS链接