题面

题意

给出一个图,图中有8个皇后,问至少移动几步才能使它满足八皇后.

方法

首先枚举八皇后问题的92种解法,算出给出图与正确图间的最小移动步数并以此更新答案
计算步数的方法:用状态dp进行两两匹配,算出两点间的最少移动次数(皇后要移动几步,移动时可无视其他皇后).
若在移动时遇到其他皇后,则可通过交换移动次序来避免此情况.

代码

#include<bits/stdc++.h>
using namespace std;
int T,TT,ans,dp[500],x[100][10],y[100][10],n1[10],n2[10],nn,an,m=8,a[10][10];
char b[10][10],ch,tmp[10];
void tiao(int gs)
{
int p,q,i,j,now=0;
if(gs==m)
{
an++;
for(p=1;p<=m;p++)
{
for(q=1;q<=m;q++)
{
if(!(a[p][q]>=2||a[p][q]==0))
{
now++;
x[an][now]=p;
y[an][now]=q;
}
}
}
}
else
{
for(p=1;p<=m;p++)
{
if(a[p][gs+1]==0)
{
a[p][gs+1]=1;
for(i=1;i<=m;i++)
{
if(a[p][i]==0)
a[p][i]=gs+2;
if(a[p-i][gs+1+i]==0&&p-i>=1&&gs+1+i<=8)
a[p-i][gs+1+i]=gs+2;
if(a[p+i][gs+1+i]==0&&p+i<=8&&gs+1+i<=8)
a[p+i][gs+1+i]=gs+2;
}
tiao(gs+1);
a[p][gs+1]=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]==gs+2) a[i][j]=0;
}
}
}
}
}
}
inline int cnt(int u)
{
int res=0;
while(u)
{
if(u & 1) res++;
u>>=1;
}
return res;
}
inline int Pd(int u1,int u2,int v1,int v2)
{
if(u1==v1&&u2==v2) return 0;
if(u1==v1||u2==v2||u1-v1==u2-v2||v1-u1==u2-v2) return 1;
return 2;
}
inline int find(int u)
{
int i,j,k,l;
for(i=1;i<=255;i++) dp[i]=100;
dp[0]=0;
for(i=0;i<=255;i++)
{
if(dp[i]==100) continue;
k=cnt(i)+1;
for(j=1;j<=8;j++)
{
if((i & (1 << (j-1)))) continue;
dp[i|(1 << (j-1))]=min(dp[i|(1 << (j-1))],dp[i]+Pd(n1[k],n2[k],x[u][j],y[u][j]));
}
}
return dp[255];
}
int main()
{
int i,j,k;
tiao(0);
/*
int now=1;
#define MM 3
for(i=1;i<=8;i++)
{
for(j=1;j<=8;j++)
{
if(i==x[MM][now]&&j==y[MM][now])
{
cout<<'q';
now++;
}
else
{
cout<<'.';
}
}
cout<<endl;
}
//*/
cin>>T;
TT=T;
while(T--)
{
nn=0;
for(i=1;i<=8;i++)
{
scanf("%s",tmp+1);
for(j=1;j<=8;j++)
{
if(tmp[j]=='q')
{
nn++;
n1[nn]=i;
n2[nn]=j;
}
}
}
/*
for(i=1;i<=nn;i++)
{
cout<<n1[i]<<" "<<n2[i]<<endl;
}
//*/
ans=100;
for(i=1;i<=92;i++)
{
ans=min(find(i),ans);
}
printf("Case %d: %dn",TT-T,ans);
}
}

最后

以上就是傻傻钢笔为你收集整理的LightOJ 1061(n皇后)题面题意方法代码的全部内容，希望文章能够帮你解决LightOJ 1061(n皇后)题面题意方法代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。