首页 > 代码库 > 【递推】【DFS】【枚举】Gym - 101246C - Explode 'Em All
【递推】【DFS】【枚举】Gym - 101246C - Explode 'Em All
网格里放了一些石块，一个炸弹能炸开其所在的行和列。问炸光石块至少要几个炸弹。
枚举不炸开的行数，则可以得出还要炸开几列。
为了不让复杂度爆炸，需要两个优化。
先是递推预处理出f(i)表示i的二进制位中1的个数，f(i)=f(i-2^k)+1，k是可以推算出来的。
还要DFS枚举不炸开的行数，防止重复访问。（类似容斥的时候的写法）
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,f[1<<25],g[1<<25],zt[26],ans=2147483647;
char a[30][30];
void dfs(int S,int cur,int now){
ans=min(ans,n-now+(f[S]-(n-now)<0 ? 0 : f[S]-(n-now)));
for(int i=cur+1;i<=n;++i){
dfs(S|zt[i],i,now+1);
}
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",a[i]+1);
for(int j=1;j<=m;++j){
if(a[i][j]==‘*‘){
zt[i]|=(1<<(j-1));
}
}
}
for(int i=1,j=0;i<(1<<m);++i){
if(i==(1<<j)){
++j;
}
f[i]=f[i-(1<<(j-1))]+1;
}
dfs(0,0,0);
printf("%d\n",ans);
return 0;
}
【递推】【DFS】【枚举】Gym - 101246C - Explode 'Em All
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。