ACM/ICCCのBFS(オフライン)+康拓展開(HDU 1430-魔板)

魔板問題は、古典的な康拓展開+BFS問題であり、便利さを実現するためにstringクラスで文字列を表すのは、これまでstringクラスをあまり使わなかった(効率的ではなく、char配列の関連関数に詳しいため)ため、ここでも無視されがちな問題がたくさん発見された.
 
 
康拓があまり知らない系を展開するには、まずブログを参照してください.http://blog.csdn.net/zhongkeli/article/details/6966805
　　
stingクラスについては,付与時にその付与位置とヘッダセットとの間に未付与部分が存在しないことに注意する.
 
テーマを変える必要があるのは、スタートマジックボード->ターゲットマジックボードを標準マジックボード->新しいターゲットマジックボードの形式に変換し、オフライン(メーター)で1回で十分になるようにする必要があります.
具体的なコードは以下の通りです.

  1 //    -BFS(  )+    
  2 //Time: 38Ms Memory:6484K
  3 #include<iostream>
  4 #include<string>
  5 #include<queue>
  6 #include<algorithm>
  7 using namespace std;
  8 
  9 #define MAX 40321
 10 
 11 int fac[8] = { 1,1,2,6,24,120,720,5040 };    //    
 12 
 13 int v[MAX];        //    
 14 string ans[MAX];    //   
 15 
 16 struct Board{
 17     int val;    //Hash 
 18     string str;
 19 };
 20 
 21 //    (Hash)
 22 int Contor(string str)
 23 {
 24     int num = 0;    //Hash 
 25     for (int i = 0; i < 8; i++)
 26     {
 27         int tmp = 0;    //          (  )
 28         for (int j = i + 1; j < 8; j++)
 29             if (str[j] < str[i]) tmp++;
 30         num += tmp*fac[7 - i];
 31     }
 32     return num;
 33 }
 34 
 35 //    (BFS)
 36 void Init()
 37 {
 38     queue<Board>Q;
 39     Board t, tmp;
 40     t.str = tmp.str = "12345678";    //    
 41     t.val = Contor(t.str);
 42     v[t.val] = 1;
 43     Q.push(t);
 44     while (!Q.empty()) {
 45         t = Q.front();
 46         Q.pop();
 47 
 48         // A:   
 49         for (int i = 0; i < 8; i++)
 50             tmp.str[(i + 4) % 8] = t.str[i];
 51 
 52         tmp.val = Contor(tmp.str);
 53         if (!v[tmp.val]) {
 54             v[tmp.val] = 1;
 55             ans[tmp.val] = ans[t.val] + 'A';
 56             Q.push(tmp);
 57         }
 58 
 59         // B:    
 60         for (int i = 0; i < 4; i++)
 61             tmp.str[(i + 1) % 4] = t.str[i];
 62         for (int i = 4; i < 8; i++)
 63             tmp.str[(i + 1) % 4 + 4] = t.str[i];
 64 
 65         tmp.val = Contor(tmp.str);
 66         if (!v[tmp.val]) {
 67             v[tmp.val] = 1;
 68             ans[tmp.val] = ans[t.val] + 'B';
 69             Q.push(tmp);
 70         }
 71 
 72         // C:      
 73         tmp.str = t.str;
 74         tmp.str[1] = t.str[5]; tmp.str[2] = t.str[1];
 75         tmp.str[6] = t.str[2]; tmp.str[5] = t.str[6];
 76 
 77         tmp.val = Contor(tmp.str);
 78         if (!v[tmp.val]) {
 79             v[tmp.val] = 1;
 80             ans[tmp.val] = ans[t.val] + 'C';
 81             Q.push(tmp);
 82         }
 83     }
 84 }
 85 
 86 int main()
 87 {
 88     Init();    //BFS
 89     string ts, te;
 90     while (cin >> ts >> te)
 91     {
 92         /*       */
 93         swap(ts[5], ts[6]);
 94         swap(ts[4], ts[7]);
 95         swap(te[5], te[6]);
 96         swap(te[4], te[7]);
 97 
 98         /*            ，           */
 99         char tmp[9];
100         for (int i = 0; i < 8; i++)
101             tmp[ts[i] - '0'] = i + '1';
102         for (int i = 0; i < 8; i++)
103             te[i] = tmp[te[i] - '0'];
104 
105         cout << ans[Contor(te)] << endl;
106     }
107 
108     return 0;
109 }