HDU 2174 Bridged Marble Rings

题目：Bridged Marble Rings

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

题意：如图，要把所有灰色球移动到上圈，每次操作可以转图中虚线圈起的三个圆，求中间圆的最少转数。题目给出的是字符串，g代表灰色球，y代表黄色球，起始位置看标记。

思路：

　　BFS打表+最小表示法

　　令g=1，y=0，用int 表示当前状态。

　　最开始直接用BFS打表，超时超内存，按我最初的算法，所有状态总数为C（26，13）约等于1000多万种。但实际上，因为转动上下两个圈是不增加转数的，所以很多情况是等价的，可以压缩状态数，对于一个状态S，可以转动上圈，下圈使其得到最小表示的状态T。接着存T就可以了。每次，注意，map会超时，后面我改成哈希就过了。。。

　　具体：每次出队一个状态，将该状态对应的13*13个下一步状态（筛选一下）入队。

AC代码：

  1 #include
  2 #include
  3 #include
  4 #include
  5 using namespace std;
  6 
  7 #define Mod 1000007     //取模的大小，哈希表的大小...
  8 #define Max 100007         //存放的总数
  9 typedef long long LL;
 10 class Hash             //手写哈希
 11 {
 12   public:
 13     int hs[Mod];       //哈希值  设定的哈希函数为 原值 % Mod ，所以哈希值有可能是 0 ~ Mod-1
 14     int next[Max];     //链表    存放哈希值相等的一条链，他的大小取决于所有原值的数量
 15     LL S[Max];         //存放原值
 16     int H[Max];        //存放所有哈希值
 17     int sn;            //不同原值的数量
 18     int hn;            //不同哈希值的数量
 19     Hash()             //构造函数: 定义Hash类变量时初始化
 20     {
 21       sn=0;
 22       hn=0;
 23       for(int i=0;i)
 24         hs[i]=0;
 25     }
 26     void clear()       //清空函数
 27     {
 28       sn=0;
 29       for(int i=0;i)
 30         hs[H[i]]=0;
 31       hn=0;
 32     }
 33     void add(LL s)           //加入
 34     {
 35       int ha=abs(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       next[sn]=hs[ha];       //原本原值记录位置
 43       hs[ha]=sn;             //最新原值记录位置，如果从0 开始存，就无法判断此时是空还是1个值
 44       //比如：5 和 10 有一样的哈希值 ，并且 5 和 10 先后加入 那么有：
 45       //5 加入: next[1] = 0; hs[5] = 1; hs[5] 是哈希值为5 的头，表示第一个原值在1的位置
 46       //10加入: next[2] = 1; hs[5] = 2; 表示第一个哈希值为5的在2，第二个在1，第三个不存在
 47     }
 48     int find(LL s)           //查找
 49     {
 50       int ha=abs(s)%Mod;     //计算哈希值
 51       int k=hs[ha];          //头
 52       while(k!=0)
 53       {
 54         if(S[k]==s) return k;//找到
 55         k=next[k];           //下一个节点
 56       }
 57       return 0;              //表示没找到
 58     }
 59 };
 60 
 61 int move(int s, int i){
 62   int gao = (s>>13)&0x1FFF;
 63   int di = s&0x1FFF;
 64   if(i==0){
 65     int tmp = di&1;
 66     di = di >> 1;
 67     di = di | (tmp << 12);
 68   }
 69   else if(i==1){
 70     int tmp = gao&1;
 71     gao = gao >> 1;
 72     gao = gao | (tmp << 12);
 73   }
 74   else{
 75     int a = (gao & 0x1C00)>>10;
 76     int b = (di & 0x1C00)>>10;
 77     gao = gao & 0x3FF;
 78     di = di & 0x3FF;
 79     gao = (b<<10)| gao;
 80     di = (a<<10) | di;
 81   }
 82   return (gao<<13)|di;
 83 }
 84 
 85 map<int, int> mp;
 86 int c[1<<13];
 87 
 88 int min_code(int s){
 89   int gao = (s>>13)&0x1FFF;
 90   int di = s&0x1FFF;
 91   gao = c[gao];
 92   di = c[di];
 93   return (gao<<13)|di;
 94 }
 95 int min_code_1(int s){
 96   int ms=s;
 97   for(int i=0; i<12; i++){
 98     int tmp = s&1;
 99     s >>= 1;
100     s = s | (tmp << 12);
101     if(ms>s) ms=s;
102   }
103   return ms;
104 }
105 
106 Hash hs;
107 queue<int> q;
108 
109 void mov(int ms){
110   int a=ms;
111   for(int i=0; i<13; i++){
112     a=move(a, 0);
113     int b=a;
114     for(int j=0; j<13; j++){
115       b=move(b, 1);
116       int c=move(b, 2);
117       int mc=min_code(c);
118       int cx=hs.find(mc);
119       if(cx==0){
120         hs.add(mc);
121         mp[mc]=mp[ms]+1;
122         q.push(mc);
123       }
124     }
125   }
126 }
127 
128 void bfs(int s){
129   s=min_code(s);
130   mp[s]=1;
131   q.push(s);
132   while(q.size()){
133     int a=q.front();
134     q.pop();
135     mov(a);
136   }
137 }
138 
139 int main(){
140   for(int i=0; i<(1<<13); i++){
141     c[i]=min_code_1(i);
142   }
143   int t=0x3FFE000;
144   bfs(t);
145   char tmp[30];
146   while(~scanf("%s", tmp)){
147     int s=0;
148     for(int i=0; tmp[i]; i++){
149       if(tmp[i]=='g') s=s*2+1;
150       else s=s*2;
151     }
152 
153     if(s==t) printf("0\n");
154     else printf("%d\n", mp[min_code(s)]-1);
155   }
156   return 0;
157 }
搜索-BFS数据结构-哈希

相关

标签