1 /* 2 題意：就是給定兩個篩子，每個篩子上6個面，每個面的數字屬于[1,6]， 且互不相同！ 3 問a篩子最少經過按照題目規定的要求轉動，達到和b篩子上下左右前后的數字相同！ 4 5 思路：很直白的bfs，將每一種狀態對應一個數字，保證這種狀態不會重新加入隊列中！ 6 */ 7 #include<iostream> 8 #include<cstdio> 9 #include<cstring> 10 #include<algorithm> 11 #include<queue> 12 using namespace std; 13 14 int a[7], ss; 15 int vis[654330]; 16 17 struct node{ 18 int k[7]; 19 node(){} 20 node(int a1, int a2, int a3, int a4, int a5, int a6){ 21 k[1]=a1; 22 k[2]=a2; 23 k[3]=a3; 24 k[4]=a4; 25 k[5]=a5; 26 k[6]=a6; 27 } 28 int step; 29 }; 30 31 queue<node>q; 32 33 34 int sum(node x){ 35 int s=0; 36 for(int i=1; i<=6; ++i) 37 s= s*10 + x.k[i]; 38 return s; 39 } 40 41 bool bfs(){ 42 while(!q.empty()) q.pop(); 43 node cur(a[1], a[2], a[3], a[4], a[5], a[6]); 44 cur.step=0; 45 q.push(cur); 46 vis[sum(cur)]=1; 47 while(!q.empty()){ 48 cur = q.front(); 49 if(sum(cur)==ss){ 50 printf("%d\n", cur.step); 51 return true; 52 } 53 q.pop(); 54 node *nt = new node(cur.k[5], cur.k[6], cur.k[3], cur.k[4], cur.k[2], cur.k[1]); 55 int v = sum(*nt); 56 if(!vis[v]){ 57 vis[v]=1; 58 nt->step = cur.step + 1; 59 q.push(*nt); 60 } 61 62 nt = new node(cur.k[6], cur.k[5], cur.k[3], cur.k[4], cur.k[1], cur.k[2]); 63 v = sum(*nt); 64 if(!vis[v]){ 65 vis[v]=1; 66 nt->step = cur.step + 1; 67 q.push(*nt); 68 } 69 70 nt = new node(cur.k[3], cur.k[4], cur.k[2], cur.k[1], cur.k[5], cur.k[6]); 71 v = sum(*nt); 72 if(!vis[v]){ 73 vis[v]=1; 74 nt->step = cur.step + 1; 75 q.push(*nt); 76 } 77 78 nt = new node(cur.k[4], cur.k[3], cur.k[1], cur.k[2], cur.k[5], cur.k[6]); 79 v = sum(*nt); 80 if(!vis[v]){ 81 vis[v]=1; 82 nt->step = cur.step + 1; 83 q.push(*nt); 84 } 85 } 86 return false; 87 } 88 89 int main(){ 90 while(scanf("%d%d%d%d%d%d", &a[1], &a[2], &a[3], &a[4], &a[5], &a[6])!=EOF){ 91 ss=0; 92 for(int i=1; i<=6; ++i){ 93 int x; 94 scanf("%d", &x); 95 ss = ss * 10 + x; 96 } 97 memset(vis, 0, sizeof(vis)); 98 if(!bfs()) 99 printf("-1\n"); 100 } 101 return 0; 102 }
?
_oracle)
