N Queen Again LightOJ

N Queen Again LightOJ - 1061

首先预处理（或打表）出所有八皇后的解法（只有92种）。然后枚举目标状态，对于每一个目标状态用一个状压dp求出到达那个状态的最小费用。到达任何一个目标状态的最小费用就是答案。

显然，已知原来8个点的位置，要到达目标8个点的位置，就是使得每一个原来点匹配一个目标点。（为什么看到就想到爆搜？然而有比爆搜更好的..）

状压dp是：

ans[S]表示用[满足(编号被包含在S集合中)条件的所有目标点]去匹配原来点中的前 |S| （表示S集合的点的个数）个点的最小费用。

对于每一个枚举出的S，此时需要被匹配的点就是原来点的第 |S| 个，那么枚举从S中选择一个目标点去匹配它，记录最小的费用。

对于每一步的费用，有一个直觉做法：

如果原来点和目标点在同一位置，那么费用为0。否则如果在同一列或同一斜线，那么费用为1。否则费用为2。

然而这个直觉做法，在想出来之后很可能会下意识就否定掉，由于可能有已经摆好的或未摆好的棋子挡路。

然而事实上是对的：（如果不对这题就没法做了吧..）http://blog.csdn.net/xiefubao/article/details/25276999

（所以说..还是要大胆猜想，暴力对拍吗....感觉某些这种猜想，提出一个看上去正确的证明，都有可能遗漏了什么呢..所以即使想出了一个证明也不一定敢用猜想）

（这题根本没办法暴力对拍呢...所以还是要抱着对自己证明的信任？）

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int pre_ans[][],num_pre;

 bool vis[],vis2[],vis3[];

 int t1[],t2[],len;

 int T,TT,now,anss,cnt;

 int ans[];

 void pre_dfs(int x)

 {

     if(x>)

     {

         ++num_pre;

         memcpy(pre_ans[num_pre],t1,sizeof(t1));

         return;

     }

     int i;

     for(i=;i<=;i++)

         if(!vis[i]&&!vis2[x-i+]&&!vis3[x+i])

         {

             vis[i]=;

             vis2[x-i+]=;

             vis3[x+i]=;

             t1[x]=i;

             pre_dfs(x+);

             vis[i]=;

             vis2[x-i+]=;

             vis3[x+i]=;

         }

 }

 int get_dis(int a,int b)

 {

     if(a==t1[b]&&pre_ans[now][a]==t2[b])    return ;

     if(a==t1[b])    return ;

     if(pre_ans[now][a]==t2[b])    return ;

     if(a+pre_ans[now][a]==t1[b]+t2[b])    return ;

     if(a-pre_ans[now][a]==t1[b]-t2[b])    return ;

     return ;

 }

 int main()

 {

     int i,j;

     char c;

     pre_dfs();

     scanf("%d",&T);

     for(TT=;TT<=T;TT++)

     {

         len=;anss=0x3f3f3f3f;

         for(i=;i<=;i++)

             for(j=;j<=;j++)

             {

                 c=getchar();

                 while(c!='.'&&c!='q')    c=getchar();

                 if(c=='q')

                 {

                     ++len;

                     t1[len]=i;

                     t2[len]=j;

                 }

             }

         for(now=;now<=num_pre;now++)

         {

             memset(ans,0x3f,sizeof(ans));

             ans[]=;

             for(i=;i<(<<);i++)

             {

                 cnt=__builtin_popcount(i);

                 for(j=;j<=;j++)

                     if(i&(<<(j-)))

                         ans[i]=min(ans[i],ans[i^(<<(j-))]+get_dis(j,cnt));

             }

             anss=min(anss,ans[(<<)-]);

         }

         printf("Case %d: %d\n",TT,anss);

     }

 }

巴特西

N Queen Again LightOJ - 1061

最新文章

热门文章