首页 > 代码库 > 2014ACMICPC西安网赛1006
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 }
本题中用到的操作：
用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\n",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\n",++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\n",++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\n",++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\n",++flag);107 ok=true;108 return;109 }110 else111 {112 if(HASH.count(C)) continue;113 else114 {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\n");137 B.clear();138 HASH.clear();139 ok=false;140 }141 }
2014ACMICPC西安网赛1006
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。