HDU 1430 魔板

题目：魔板

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1430

题意：（中文题）

思路：

　　BFS哈希打表+映射

　　哇。。好题啊，映射没想到。由于题目是求状态S到状态T的最短路，所以一开始就把打表排除了，后来看题解说可以映射+打表，因为每一步的行动和数字没关系，因此假设给出的是87654321，可以把8当作1，7当作2，。。。，1当作8，然后对T也作相应变化，这样一来，就可以用12345678广搜打表。

AC代码：

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<string>
  4 #include<queue>
  5 #include<iostream>
  6 using namespace std;
  7 #define Mod 1000007    //取模的大小，哈希表的大小...
  8 #define Max 100007     //存放的总数
  9 
 10 class Hash             //手写哈希
 11 {
 12   public:
 13     int hs[Mod];       //哈希值  设定的哈希函数为 原值 % Mod ，所以哈希值有可能是 0 ~ Mod-1
 14     int next[Max];     //链表    存放哈希值相等的一条链，他的大小取决于所有原值的数量
 15     int S[Max];        //存放原值
 16     string V[Max];     //存放原值对应的val值
 17     int H[Max];        //存放所有哈希值
 18     int sn;            //不同原值的数量
 19     int hn;            //不同哈希值的数量
 20     Hash()             //构造函数: 定义Hash类变量时初始化
 21     {
 22       sn=0;
 23       hn=0;
 24       memset(hs, 0, sizeof(hs));
 25     }
 26     void clear()       //清空函数
 27     {
 28       sn=0;
 29       for(int i=0;i<hn;i++)
 30         hs[H[i]]=0;
 31       hn=0;
 32     }
 33     void add(int s, string val) //加入
 34     {
 35       int ha=s%Mod;          //计算哈希值
 36       if(hs[ha]==0)          //如果该哈希值还未出现过
 37       {
 38         H[hn++]=ha;          //将该哈希值记录起来，同时哈希值数量加 1
 39       }
 40       sn++;                  //0 表示结尾，所以从1 开始存，原值数量加 1，特别针对 hs数组
 41       S[sn]=s;               //将原值记录起来
 42       V[sn]=val;
 43       next[sn]=hs[ha];       //原本原值记录位置
 44       hs[ha]=sn;             //最新原值记录位置，如果从0 开始存，就无法判断此时是空还是1个值
 45 
 46       //比如：5 和 10 有一样的哈希值 ，并且 5 和 10 先后加入 那么有：
 47       //5 加入: next[1] = 0; hs[5] = 1; hs[5] 是哈希值为5 的头，表示第一个原值在1的位置
 48       //10加入: next[2] = 1; hs[5] = 2; 表示第一个哈希值为5的在2，第二个在1，第三个不存在
 49     }
 50     int find(int s)           //查找
 51     {
 52       int ha=s%Mod;     //计算哈希值
 53       int k=hs[ha];          //头
 54       while(k!=0)
 55       {
 56         if(S[k]==s) return 1;//找到
 57         k=next[k];           //下一个节点
 58       }
 59       return 0;              //表示没找到
 60     }
 61     string get(int s){
 62       int ha=s%Mod;     //计算哈希值
 63       int k=hs[ha];          //头
 64       while(k!=0)
 65       {
 66         if(S[k]==s) return V[k];//找到
 67         k=next[k];           //下一个节点
 68       }
 69       return "";              //表示没找到
 70     }
 71 };
 72 
 73 int change(int s){
 74   return s%10*1000 + s%100/10*100 + s%1000/100*10 + s%10000/1000;
 75 }
 76 
 77 int move(int s, int i){
 78   int gao = s/10000;
 79   int di = change(s%10000);
 80   if(i==1) return di*10000+change(gao);
 81   else if(i==2){
 82     gao = gao/10 + gao%10*1000;
 83     di = di/10 + di%10*1000;
 84   }
 85   else if(i==3){
 86     int tmp1 = gao%1000/10*10;
 87     int tmp2 = di%1000/10*10;
 88     gao -= tmp1;
 89     di -= tmp2;
 90     gao += tmp2/100*100 + tmp1/100*10;
 91     di += tmp2%100/10*100 + tmp1%100/10*10;
 92   }
 93   return gao*10000+change(di);
 94 }
 95 
 96 string get(int i){
 97   if(i==1) return "A";
 98   else if(i==2) return "B";
 99   else return "C";
100 }
101 
102 Hash hs;
103 queue<int> q;
104 void bfs(int s){
105   hs.add(s, "");
106   q.push(s);
107   while(q.size()){
108     int a=q.front();
109     q.pop();
110     string ax=hs.get(a);
111     for(int i=1; i<=3; i++){
112       int b=move(a, i);
113 
114       if(hs.find(b)==0){
115         hs.add(b, ax+get(i));
116         q.push(b);
117       }
118     }
119   }
120 }
121 
122 int main(){
123   bfs(12345678);
124   int s, t;
125   while(~scanf("%d%d", &s, &t)){
126     int c[10], k=1;
127     for(int i=0; i<8; i++){
128       c[s/k%10]=8-i;
129       k=k*10;
130     }
131     k=1;
132     for(int i=0; i<8; i++){
133       t=t-t/k%10*k+c[ t/k%10 ]*k;
134       k=k*10;
135     }
136 
137     cout << hs.get(t) << endl;
138   }
139   return 0;
140 }