題意略。
思路：簡單的四方向BFS，用map記錄去重。
總結：WA了一發因為骰子面的變換寫錯了一個地方。要細心。
AC代碼（Exe.Time: 31ms）：
1 #include <iostream>
2 #include <cstdio>
3 #include <vector>
4 #include <algorithm>
5 #include <map>
6 #include <queue>
7 using namespace std;
8
9 struct node
10 {
11 int up, dn, l, r, fr, bk;
12 int num;
13 bool operator == (const node x) const
14 {
15 bool re = (up == x.up && dn == x.dn && l == x.l && r == x.r && fr == x.fr && bk == x.bk);
16 return re;
17 }
18 bool operator < (const node x) const
19 {
20 if(up == x.up) {
21 if(dn == x.dn) {
22 if(l == x.l) {
23 if(r == x.r) {
24 return fr < x.fr;
25 }
26 return r < x.r;
27 }
28 return l < x.l;
29 }
30 return dn < x.dn;
31 }
32 return up < x.up;
33 }
34 };
35 void Swap(int &a, int &b)
36 {
37 a = a^b;
38 b = a^b;
39 a = a^b;
40 }
41 node arr, brr;
42 void change_lr(node &x)
43 {
44 Swap(x.l, x.dn);
45 Swap(x.r, x.up);
46 Swap(x.l, x.r);
47 }
48 void change_rr(node &x)
49 {
50 Swap(x.up, x.r);
51 Swap(x.dn, x.l);
52 Swap(x.up, x.dn);
53 }
54 void change_br(node &x)
55 {
56 Swap(x.up, x.fr);
57 Swap(x.dn, x.bk);
58 Swap(x.fr, x.bk);
59 }
60 void change_fr(node &x)
61 {
62 Swap(x.up, x.fr);
63 Swap(x.dn, x.bk);
64 Swap(x.dn, x.up);
65 }
66 void print(node x)
67 {
68 cout<<x.up<<" "<<x.dn<<" "<<x.l<<" "<<x.r<<" "<<x.fr<<" "<<x.bk<<endl;
69 }
70 void bfs(node cont, int &num)
71 {
72 int cnt = 0;
73 queue<node> q;
74 map<node, int> vis;
75 map<node, int>::iterator it;
76 vis.insert(pair<node, int> (cont, cnt++));
77 q.push(cont);
78 while(!q.empty()) {
79 node fro = q.front(); q.pop();
80 if(fro == brr) { num = fro.num; return; }
81 node x;
82 for(int i = 0; i < 4; i++ ){
83 x = fro;
84 x.num = fro.num+1;
85 if(i == 0) change_br(x);
86 else if(i == 1) change_fr(x);
87 else if(i == 2) change_lr(x);
88 else if(i == 3) change_rr(x);
89 it = vis.find(x);
90 if(it == vis.end()) {
91 vis.insert(pair<node, int> (x, cnt++));
92 q.push(x);
93 }
94 }
95 }
96 num = -1;
97 }
98
99 int main()
100 {
101 node a;
102 while(scanf("%d%d%d%d%d%d", &a.up, &a.dn, &a.l, &a.r, &a.fr, &a.bk) != EOF) {
103 a.num = 0;
104 arr = a;
105 scanf("%d%d%d%d%d%d", &a.up, &a.dn, &a.l, &a.r, &a.fr, &a.bk);
106 brr = a;
107 int ans;
108 bfs(arr, ans);
109 printf("%d\n", ans);
110 }
111 } View Code
轉載于:https://www.cnblogs.com/ZiningTang/p/3973332.html