|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; struct diceType{ int dice[6]; int cnt; diceType(int *a,int count){ memcpy(dice, a, sizeof(dice)); cnt = count; } }; void roll_left(int *dice){ int a = dice[0]; int b = dice[1]; int c = dice[2]; int d = dice[3]; int e = dice[4]; int f = dice[5]; dice[0] = d; dice[1] = c; dice[2] = a; dice[3] = b; dice[4] = e; dice[5] = f; } void roll_right(int *dice){ int a = dice[0]; int b = dice[1]; int c = dice[2]; int d = dice[3]; int e = dice[4]; int f = dice[5]; dice[0] = c; dice[1] = d; dice[2] = b; dice[3] = a; dice[4] = e; dice[5] = f; } void roll_front(int *dice){ int a = dice[0]; int b = dice[1]; int c = dice[2]; int d = dice[3]; int e = dice[4]; int f = dice[5]; dice[0] = f; dice[1] = e; dice[2] = c; dice[3] = d; dice[4] = a; dice[5] = b; } void roll_back(int *dice){ int a = dice[0]; int b = dice[1]; int c = dice[2]; int d = dice[3]; int e = dice[4]; int f = dice[5]; dice[0] = e; dice[1] = f; dice[2] = c; dice[3] = d; dice[4] = b; dice[5] = a; } bool compare_dice(int *a,int *b){ for (int i = 0; i < 6; i++) { if (a[i] != b[i]) { return false; } } return true; } int main(){ int orig[6],goal[6]; while (cin >> orig[0]) { for (int i = 1; i < 6; i++) { cin >> orig[i]; } for (int i = 0; i < 6; i++) { cin >> goal[i]; } diceType init(orig,0); queue<diceType> q; q.push(init); int res = -1; while (!q.empty()) { diceType now = q.front(); q.pop(); if (now.cnt >= 5) { continue; } if (compare_dice(goal, now.dice)) { res = now.cnt; break; } now.cnt++; roll_left(now.dice); q.push(now); roll_right(now.dice); roll_right(now.dice); q.push(now); roll_left(now.dice); roll_front(now.dice); q.push(now); roll_back(now.dice); roll_back(now.dice); q.push(now); roll_front(now.dice); } cout << res << endl; } return 0; } |
不科学的剪枝，当深度到5就放弃当前节点，然后居然过了，可见数据水了。
科学的做法是把骰子的6个面的状态连一起当成整数，开个标记数组，就跟hash一样。
