2014ACMICPC西安网赛1006

题意：给你一个骰子的初始状态和可以进行的四种操作，求从初始状态到目标状态的最少操作次数

题目本身很简单，bfs即可。但是因为骰子有六个面，搜索判重和记录状态比较麻烦。这时候就需要神器STL了。

  1 #include <iostream>
  2 #include <map>
  3 #include <queue>
  4 #include <vector>
  5 #include <algorithm>
  6 #include <cstdio>
  7 #include <cstring>
  8 using namespace std;
  9 
 10 struct node
 11 {
 12     vector<int> seq;
 13     int step;
 14     node(vector<int> x,int m):seq(x),step(m)
 15     {}
 16 };
 17 
 18 int a[10],b[10];
 19 vector<int> A;
 20 vector<int> y;
 21 //queue<node> Q;
 22 map<vector<int>,int> M;
 23 bool ok;
 24 
 25 void writeln(vector<int> x,node y)
 26 {
 27     for (int i=0;i<6;i++)
 28         cout<<x[i]<<" ";
 29     cout<<" - "<<y.step<<endl;
 30 }
 31 
 32 bool satisfy()
 33 {
 34     for (int i=0;i<6;i++)
 35         if (y[i]!=b[i])     return false;
 36     ok=true;
 37     return true;
 38 }
 39 
 40 void lft()
 41 {
 42     vector<int> t;
 43     t=y;
 44     y[2]=t[0];    y[3]=t[1];    y[1]=t[2];
 45     y[0]=t[3];    y[4]=t[4];    y[5]=t[5];
 46 }
 47 void rht()
 48 {
 49     vector<int> t;
 50     t=y;
 51     y[3]=t[0];    y[2]=t[1];    y[0]=t[2];
 52     y[1]=t[3];    y[4]=t[4];    y[5]=t[5];
 53 }
 54 void fnt()
 55 {
 56     vector<int> t;
 57     t=y;
 58     y[4]=t[0];    y[5]=t[1];    y[2]=t[2];
 59     y[3]=t[3];    y[1]=t[4];    y[0]=t[5];
 60 }
 61 void bak()
 62 {
 63     vector<int> t;
 64     t=y;
 65     y[5]=t[0];    y[4]=t[1];    y[2]=t[2];
 66     y[3]=t[3];    y[0]=t[4];    y[1]=t[5];
 67 }
 68 
 69 bool same()
 70 {
 71     for (int i=0;i<6;i++)
 72         if (a[i]!=b[i])     return false;
 73     return true;
 74 }
 75 
 76 int main()
 77 {
 78     //freopen("in.txt","r",stdin);
 79 
 80     while (cin>>a[0])
 81     {
 82         A.clear();
 83         M.clear();
 84         //Q.clear();
 85         queue <node> Q;
 86         ok=false;
 87 
 88         A.push_back(a[0]);
 89         for (int i=1;i<6;i++)
 90         {
 91             cin>>a[i];
 92             A.push_back(a[i]);
 93         }
 94         for (int i=0;i<6;i++)
 95             cin>>b[i];
 96         if (same())
 97         {
 98             cout<<0<<endl;
 99             continue;
100         }
101 
102         Q.push(node(A,1));
103         //int nm=1;
104         M.insert(pair<vector<int>,int>(A,1));
105 
106         while (!Q.empty())
107         {
108             node tmp=Q.front();
109             Q.pop();
110             int st=tmp.step;
111             st++;
112             y=tmp.seq;
113             //writeln(y,tmp); ////////
114             if (satisfy())
115             {
116                 cout<<st-2<<endl;
117                 break;
118             }
119             /*
120             if (st>55)
121             {
122                 cout<<-1<<endl;
123                 break;
124             }*/
125             for (int tm=1;tm<=4;tm++)
126             {
127                 if (tm==1)
128                 {
129                     y=tmp.seq;
130                     lft();
131                     if (!M.count(y))
132                     {
133                         M.insert(pair<vector<int>,int>(y,1));
134                         Q.push(node(y,st));
135                     }
136                 }
137                 if (tm==2)
138                 {
139                     y=tmp.seq;
140                     rht();
141                     if (!M.count(y))
142                     {
143                         M.insert(pair<vector<int>,int>(y,1));
144                         Q.push(node(y,st));
145                     }
146                 }
147                 if (tm==3)
148                 {
149                     y=tmp.seq;
150                     fnt();
151                     if (!M.count(y))
152                     {
153                         M.insert(pair<vector<int>,int>(y,1));
154                         Q.push(node(y,st));
155                     }
156                 }
157                 if (tm==4)
158                 {
159                     y=tmp.seq;
160                     bak();
161                     if (!M.count(y))
162                     {
163                         M.insert(pair<vector<int>,int>(y,1));
164                         Q.push(node(y,st));
165                     }
166                 }
167             }
168         }
169         if (!ok)    cout<<-1<<endl;
170     }
171 
172 }

View Code

本题中用到的操作：

用map作为哈希表判重：

map<vector<int>,int>，这样就把一个vector容器和一个整数关联起来了。

map对象的.count(x)函数：返回x在哈希表中的出现次数，未出现则返回0。用这个函数就可以判重了。

queue：队列

注意queue和stack没有.clear()函数，所以用完之后没法清空，只能建一个新的（三次都WA到这里了，对拍时才发现T^T）

还有结构体声明里面的node(vector<int> x,int m)那个东西是结构体构造函数，neopenx大神教的，可以避免代码太屎

附上neopenx大神的AC代码，Orz

  1 #include "cstdio"
  2 #include "queue"
  3 #include "vector"
  4 #include "map"
  5 using namespace std;
  6 int a[7],b[7];
  7 vector<int> B;
  8 map<vector<int>,int> HASH;
  9 bool ok=false;
 10 struct node
 11 {
 12     vector<int> X;
 13     int num;
 14     node(vector<int> x,int n): X(x),num(n) {}
 15 };
 16 void bfs()
 17 {
 18     vector<int> A;
 19     for(int i=1;i<=6;i++) A.push_back(a[i]);
 20     if(A==B) {printf("%d
",0);ok=true;return;}
 21     queue<node> Q;Q.push(node(A,0));
 22     while(!Q.empty())
 23     {
 24         node x=Q.front();Q.pop();
 25         //if(x.num>=8) continue; //没必要对dep剪枝了，目测数据在dep=4的时候，就能全部被hash掉
 26         vector<int> tt=x.X;
 27         for(int s=0;s<4;s++)
 28         {
 29             int flag=x.num;
 30             if(s==0)
 31             {
 32                 int a=tt[0],b=tt[1],c=tt[2],d=tt[3];
 33                 vector<int> C;
 34                 C.push_back(c);C.push_back(d);C.push_back(b);C.push_back(a);
 35                 C.push_back(tt[4]);C.push_back(tt[5]);
 36                 if(C==B)
 37                 {
 38                     printf("%d
",++flag);
 39                     ok=true;
 40                     return;
 41                 }
 42                 else
 43                 {
 44                     if(HASH.count(C)) continue;
 45                     else
 46                     {
 47                        HASH[C]=1;
 48                        Q.push(node(C,++flag));
 49                     }
 50                 }
 51             }
 52             if(s==1)
 53             {
 54                 int a=tt[0],b=tt[1],c=tt[2],d=tt[3];
 55                 vector<int> C;
 56                 C.push_back(d);C.push_back(c);C.push_back(a);C.push_back(b);
 57                 C.push_back(tt[4]);C.push_back(tt[5]);
 58                  if(C==B)
 59                 {
 60                     printf("%d
",++flag);
 61                     ok=true;
 62                     return;
 63                 }
 64                 else
 65                 {
 66                     if(HASH.count(C)) continue;
 67                     else
 68                     {
 69                        HASH[C]=1;
 70                        Q.push(node(C,++flag));
 71                     }
 72                 }
 73             }
 74             if(s==2)
 75             {
 76                 int a=tt[0],b=tt[1],c=tt[4],d=tt[5];
 77                 vector<int> C;
 78                 C.push_back(c);C.push_back(d);
 79                 C.push_back(tt[2]);C.push_back(tt[3]);
 80                 C.push_back(b);C.push_back(a);
 81                  if(C==B)
 82                 {
 83                     printf("%d
",++flag);
 84                     ok=true;
 85                     return;
 86                 }
 87                 else
 88                 {
 89                     if(HASH.count(C)) continue;
 90                     else
 91                     {
 92                        HASH[C]=1;
 93                        Q.push(node(C,++flag));
 94                     }
 95                 }
 96             }
 97             if(s==3)
 98             {
 99                 int a=tt[0],b=tt[1],c=tt[4],d=tt[5];
100                 vector<int> C;
101                 C.push_back(d);C.push_back(c);
102                 C.push_back(tt[2]);C.push_back(tt[3]);
103                 C.push_back(a);C.push_back(b);
104                 if(C==B)
105                 {
106                     printf("%d
",++flag);
107                     ok=true;
108                     return;
109                 }
110                 else
111                 {
112                     if(HASH.count(C)) continue;
113                     else
114                     {
115                        HASH[C]=1;
116                        Q.push(node(C,++flag));
117                     }
118                 }
119             }
120         }
121     }
122 }
123 int main()
124 {
125     //freopen("in.txt","r",stdin);
126     while(~scanf("%d",&a[1]))
127     {
128         for(int i=2;i<=6;i++)
129             scanf("%d",&a[i]);
130         for(int i=1;i<=6;i++)
131         {
132             scanf("%d",&b[i]);
133             B.push_back(b[i]);
134         }
135         bfs();
136         if(!ok) printf("-1
");
137         B.clear();
138         HASH.clear();
139         ok=false;
140     }
141 }

View Code