首页 > > 程序设计 > C/C++ >

N Queen Again LightOJ - 1061

2018-06-27 10:03:47来源：未知阅读 ()

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

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

状压dp是：

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

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

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

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

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

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

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

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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int pre_ans[100][9],num_pre;
 6 bool vis[9],vis2[100],vis3[100];
 7 int t1[9],t2[9],len;
 8 int T,TT,now,anss,cnt;
 9 int ans[300];
10 void pre_dfs(int x)
11 {
12     if(x>8)
13     {
14         ++num_pre;
15         memcpy(pre_ans[num_pre],t1,sizeof(t1));
16         return;
17     }
18     int i;
19     for(i=1;i<=8;i++)
20         if(!vis[i]&&!vis2[x-i+50]&&!vis3[x+i])
21         {
22             vis[i]=1;
23             vis2[x-i+50]=1;
24             vis3[x+i]=1;
25             t1[x]=i;
26             pre_dfs(x+1);
27             vis[i]=0;
28             vis2[x-i+50]=0;
29             vis3[x+i]=0;
30         }
31 }
32 int get_dis(int a,int b)
33 {
34     if(a==t1[b]&&pre_ans[now][a]==t2[b])    return 0;
35     if(a==t1[b])    return 1;
36     if(pre_ans[now][a]==t2[b])    return 1;
37     if(a+pre_ans[now][a]==t1[b]+t2[b])    return 1;
38     if(a-pre_ans[now][a]==t1[b]-t2[b])    return 1;
39     return 2; 
40 }
41 int main()
42 {
43     int i,j;
44     char c;
45     pre_dfs(1);
46     scanf("%d",&T);
47     for(TT=1;TT<=T;TT++)
48     {
49         len=0;anss=0x3f3f3f3f;
50         for(i=1;i<=8;i++)
51             for(j=1;j<=8;j++)
52             {
53                 c=getchar();
54                 while(c!='.'&&c!='q')    c=getchar();
55                 if(c=='q')
56                 {
57                     ++len;
58                     t1[len]=i;
59                     t2[len]=j;
60                 }
61             }
62         for(now=1;now<=num_pre;now++)
63         {
64             memset(ans,0x3f,sizeof(ans));
65             ans[0]=0;
66             for(i=1;i<(1<<8);i++)
67             {
68                 cnt=__builtin_popcount(i);
69                 for(j=1;j<=8;j++)
70                     if(i&(1<<(j-1)))
71                         ans[i]=min(ans[i],ans[i^(1<<(j-1))]+get_dis(j,cnt));
72             }
73             anss=min(anss,ans[(1<<8)-1]);
74         }
75         printf("Case %d: %d\n",TT,anss);
76     }
77 }