POJ2286-The Rotation Game（IDDFS）迭代加深dfs

题意：http://poj.org/problem?id=2286

像密码锁一样可以转转转

问你中间8个都一样的最小步数

思路：

状态不好计，就dfs了！

剪枝：一个类似A*的f=g+h的函数（61行）

据说最多6次操作？？

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <string>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <cmath>
 9 #include <vector>
10 #include <stack>
11 #include <queue>
12 #include <list>
13 #define the_best_pony "Rainbow Dash"
14 
15 using namespace std;
16 
17 int rot[10][10]={                //操作打表
18         {0,2,6,11,15,20,22},         //A
19         {1,3,8,12,17,21,23},         //B
20         {10,9,8,7,6,5,4},            //C
21         {19,18,17,16,15,14,13},     //D
22         {23,21,17,12,8,3,1},        //E
23         {22,20,15,11,6,2,0},         //F
24         {13,14,15,16,17,18,19},     //G
25         {4,5,6,7,8,9,10}             //H
26 };
27 int cent[10]={6,7,8,11,12,15,16,17}; //中间8个位置
28 int a[30],maxh=1;
29 char put[100001];
30 
31 bool check(){ //判断中间是否一样
32     for(int i=0;i<8;i++)
33         if(a[cent[0]]!=a[cent[i]]) return false;
34     return true;
35 }
36 
37 int cnt(){
38     int num=~0u>>1;
39     for(int i=1;i<=3;i++){
40         int tmp=0;
41         for(int j=0;j<8;j++)
42             if(a[cent[j]]!=i) tmp++;
43         num=min(num,tmp);
44     }
45     return num;
46 }
47 
48 void move(int x){ //操作
49     int tmp=a[rot[x][0]];
50     for(int i=0;i<6;i++) a[rot[x][i]]=a[rot[x][i+1]];
51     a[rot[x][6]]=tmp;
52     return;
53 }
54 
55 bool dfs(int dep){
56     if(dep>maxh) return false;
57     if(check()){
58         put[dep]='';
59         return true;
60     }
61     if(dep+cnt()>maxh) return false; //乐观估计剪枝
62     for(int i=0;i<8;i++){
63         put[dep]='A'+i;
64         move(i);
65         if(dfs(dep+1)) return true;
66         if(i%2==0) move((i+5)%8);     //反向操作
67         else move((i+3)%8);        //反向操作
68     }
69     return false;
70 }
71 
72 int main(){
73     while(scanf("%d",&a[0])&&a[0]){
74         maxh=1;
75         for(int i=1;i<24;i++) scanf("%d",&a[i]);
76         if(check()) printf("No moves needed
%d
",a[cent[0]]);
77         else{
78             while(!dfs(0)) maxh++;
79             printf("%s
%d
",put,a[cent[0]]);
80         }
81     }
82     return 0;
83 }