UESTC_魔法少女小蟹 CDOJ 710

小蟹是一名魔法少女，能熟练的施放很多魔法。

有一天魔法学院上课的时候出现了这样一道题，给一个

小蟹翻了下魔法书，发现她有以下

将当前魔杖指向的数字与最左端的一个数字调换位置。
将当前魔杖指向的数字与最右端的一个数字调换位置。
将当前魔杖指向的数字
将当前魔杖指向的数字
将当前魔杖向右移动一位。
将当前魔杖向左移动一位。

最开始，她的魔杖指向的是最左边的数字。

于是小蟹很好奇，以她的能力，施展几次魔法能完成老师的这道题呢？

Input

多组数据，请处理至文件结束

对于每组数据，包含两个

Output

对于每组数据，输出一个数，代表最少施展魔法的次数。

Sample input and output

Sample Input	Sample Output
123456 654321	11

解题报告

不好想。。肯定不能处理操作3和操作4，那样bfs直接爆炸。。。本题连A*也不行。。因为状态数实在太多，又是多Case。。

难保不TLE，因此我们预处理出魔杖能到达地方的状态，之后扫一遍所有状态，加上差值就完辣

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <cstdio>
  5 using namespace std;
  6 
  7 const int MaxHashSize = 1526597;
  8 const int MaxStatusSize = 5000000;
  9 typedef struct status
 10 {
 11 int step,value;    
 12 bool arrive[6];
 13 };
 14 
 15 
 16 int Head[MaxHashSize];
 17 int Next[MaxStatusSize];
 18 status st[MaxStatusSize];
 19 int caculate[7] = {1000000,100000,10000,1000,100,10,1};
 20 int tar_num[6];
 21 
 22 void Hash_init()
 23 {
 24  memset(Head,-1,sizeof(Head));    
 25 }
 26 
 27 int GetHashNum(int& x)
 28 {
 29  return x % MaxHashSize;    
 30 }
 31 
 32 bool insert_Hash(int id)
 33 {
 34  int h = GetHashNum(st[id].value);
 35  int t = Head[h];
 36  while(t != -1)
 37  {
 38      if(st[id].value == st[t].value)
 39       return false;
 40     t = Next[t];
 41  }
 42  Next[id] = Head[h];
 43  Head[h] = id;    
 44  return true;
 45 }
 46 
 47 
 48 
 49 int bfs()
 50 {
 51  int front = 0,rear = 1;
 52  insert_Hash(0);
 53  while(front < rear)
 54   {
 55       status ss = st[front++];
 56       int num[7];
 57       int ori = ss.value;
 58       for(int i = 6 ; i >=0 ; --i)
 59         {
 60           num[i] = ss.value % 10;
 61         ss.value /= 10; 
 62        }
 63     int pos = num[6];
 64     bool flag = true;
 65     if (num[pos] == 0 || pos == 0) flag = false;
 66     if (flag)
 67      {  
 68         st[rear] = ss;
 69          int temp = num[0];
 70          num[0] = num[pos];
 71          num[pos] = temp;
 72          int value = 0;
 73          for(int i = 0 ; i < 7 ; ++ i)
 74           value += (num[i]*caculate[i]);
 75            st[rear].value = value;        
 76            if (insert_Hash(rear))
 77               {
 78                   st[rear].step = ss.step + 1;
 79                   st[rear++].arrive[0] = true;
 80               }                       
 81              num[pos] = num[0];
 82              num[0] = temp;
 83      }
 84    flag = true;
 85    if (num[5]  == 0 && pos == 0) flag = false;
 86    if (pos == 5) flag = false;
 87    if (flag)
 88     {
 89           st[rear] = ss;
 90        int temp  = num[5];
 91        num[5] = num[pos];
 92        num[pos] = temp;
 93        int value = 0;
 94        for(int i = 0 ; i < 7 ; ++ i)
 95           value += (num[i]*caculate[i]);
 96            st[rear].value = value;
 97            if (insert_Hash(rear))
 98               {
 99                  st[rear].step = ss.step + 1;
100                  st[rear++].arrive[5] = true;
101              }                 
102           num[pos] = num[5];
103              num[5] = temp;
104     }
105    if (pos < 5)
106     {
107         st[rear] = ss;
108         int value = ori + 1;
109         st[rear].value = value;
110         if (insert_Hash(rear))
111          {
112              st[rear].step = ss.step + 1;
113             st[rear++].arrive[pos+1] = true;    
114           }            
115     }
116    if (pos > 0)
117     {
118         st[rear] = ss;
119         int value = ori - 1;
120         st[rear].value = value;
121         if (insert_Hash(rear))
122          {
123              st[rear].step = ss.step + 1;
124              st[rear++].arrive[pos-1] = true;
125           }           
126     }
127   }    
128  return rear;
129 }
130 
131 
132 int slove(int x)
133 {
134  int Mo = 999;
135  for(int i = 0 ; i < x; ++ i)
136   {
137       //cout << "i is " << i << endl;
138       int num[6];
139       st[i].value /= 10;
140       int ori = st[i].value;
141       for(int j = 5;j >=0 ;--j)
142         {
143           num[j] = st[i].value % 10;
144           st[i].value /= 10;
145        }
146     int res = st[i].step;
147     for(int k = 0 ; k < 6;++k)
148      if (tar_num[k] != num[k] && !st[i].arrive[k])
149       {
150           res = 999;
151           break;
152       }
153      else
154      res += (abs(tar_num[k]-num[k]));
155     //cout << "Res is " << res << endl;
156     Mo = min(Mo,res);
157   }
158 return Mo;
159 }
160 
161 
162 int main(int argc, char * argv[])
163 {
164  int s1,s2;
165  while(scanf("%d%d",&s1,&s2) == 2)
166   {
167       Hash_init();
168       st[0].value = s1*10;
169       st[0].step = 0;
170       memset(st[0].arrive,false,sizeof(st[0].arrive));
171       st[0].arrive[0] = true;
172       for(int i = 5;i>=0;--i)
173         {
174            tar_num[i] = s2 % 10;
175            s2 /= 10;
176        }
177       cout << slove(bfs()) << endl;
178   }
179  return 0;    
180 }

No Pain , No Gain.