输入要给n*m的棋盘 均小于10 某些格子有标记 用最少的皇后 辐射到所有的标记
限时 6666ms
用IDA* 时间6000 尴尬。
#include<bits/stdc++.h> using namespace std; #define N 10 int n,m; int mp[N][N]; int cnt; int visn[N]; int vism[N]; int visx[2*N]; bool dfs(int d,int maxx) { if(cnt==0)return true; if(d==maxx)return false; if( (maxx-d)*( 3*n+m-3 ) <cnt )return false;//毫无用处。。 int oldmap[N][N];//一定要开到里面 一开始开到外面错了！ memcpy(oldmap,mp,sizeof mp); int oldcnt=cnt; for(int i=1;i<=n;i++) if(!visn[i]) for(int j=1;j<=m;j++) if(!vism[j]) { visn[i]=vism[j]=visx[i+j]=1; for(int k=1;k<=n;k++) if(mp[k][j])cnt--,mp[k][j]=0; for(int k=1;k<=m;k++) if(mp[i][k])cnt--,mp[i][k]=0; for(int k=1;k<=n;k++) for(int s=1;s<=m;s++) { if( (s-k)==(j-i)||(s+k)==(i+j) ) if(mp[k][s]) mp[k][s]=0,cnt--; } if(cnt!=oldcnt) if(dfs(d+1,maxx))return true; memcpy(mp,oldmap,sizeof mp); cnt=oldcnt; visn[i]=vism[j]=0; } return false; } int solve() { if(cnt==0)return 0; for(int maxx=1;;maxx++){ memset(visn,0,sizeof visn); memset(vism,0,sizeof vism); if(dfs(0,maxx) )return maxx; } } int main() { int cas=0; while(scanf("%d",&n),n) { cnt=0; scanf("%d",&m);getchar(); char ch; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%c",&ch); if(ch=='X')mp[i][j]=1,cnt++; } getchar(); } printf("Case %d: %d ",++cas,solve()); } }
每次dfs都要扫面落子的四个方位实在太费时间 真的铁脑残
应该像八皇后问题那样 设置标记数组就好了！！ 900ms
#include<bits/stdc++.h> using namespace std; #define N 10 int n,m; int mp[N][N]; int cnt; int visn[N]; int vism[N]; int visx[3*N]; int visy[3*N]; bool judge() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]&&!visn[i]&&!vism[j]&&!visx[i+j]&&!visy[i-j+10])return false; return true; } bool dfs(int d,int maxx) { if(judge())return true; if(d==maxx)return false; for(int i=1;i<=n;i++) if(!visn[i]) for(int j=1;j<=m;j++) if(!vism[j]) { visn[i]=vism[j]=1; int a=visx[i+j], b=visy[i-j+10]; visx[i+j]=visy[i-j+10]=1; if(dfs(d+1,maxx))return true; visn[i]=vism[j]=0; visx[i+j]=a;visy[i-j+10]=b; } return false; } int solve() { if(cnt==0)return 0; for(int maxx=1;;maxx++){ memset(visn,0,sizeof visn); memset(vism,0,sizeof vism); memset(visx,0,sizeof visx); memset(visy,0,sizeof visy); if(dfs(0,maxx) )return maxx; } } int main() { int cas=0; while(scanf("%d",&n),n) { cnt=0; scanf("%d",&m);getchar(); char ch; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%c",&ch); if(ch=='X')mp[i][j]=1,cnt++; else mp[i][j]=0; } getchar(); } printf("Case %d: %d ",++cas,solve()); } }
对行数进行优化 使行数升序：90ms 可以保证没有重复 ！！！ 上面那个代码有很多重复
#include<bits/stdc++.h> using namespace std; #define N 10 #define maxn 12 int n,m; int mp[N][N]; int cnt; int visn[N]; int vism[N]; int visx[3*N]; int visy[3*N]; int maxx; bool judge() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]&&!visn[i]&&!vism[j]&&!visx[i+j]&&!visy[i-j+10])return false; return true; } bool dfs(int d,int raw) { if(judge())return true; if(d==maxx)return false; for(int i=raw;i<=n;i++) for(int j=1;j<=m;j++) { int c=visn[i],d1=vism[j],a=visx[i+j], b=visy[i-j+10]; visx[i+j]=visy[i-j+10]=visn[i]=vism[j]=1; if(dfs(d+1,i+1))return true; visn[i]=c,vism[j]=d1; visx[i+j]=a;visy[i-j+10]=b; } return false; } int solve() { for( maxx=0;;maxx++){ memset(visn,0,sizeof visn); memset(vism,0,sizeof vism); memset(visx,0,sizeof visx); memset(visy,0,sizeof visy); if(dfs(0,1) )return maxx; } } int main() { int cas=0; while(scanf("%d",&n),n) { scanf("%d",&m);getchar(); char ch; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%c",&ch); if(ch=='X')mp[i][j]=1; else mp[i][j]=0; } getchar(); } printf("Case %d: %d ",++cas,solve()); } }