N Queen Again LightOJ - 1061

2018-06-17 21:41:30来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

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

 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 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c++作业:输入两个整数,用函数求两数之和。函数外部声明有什么

下一篇:Flv的结构分析