洛谷题号：P2730
THUOJ上也有这道题目，题目输入输出格式略微有不同，基本原理相同。但是THUOJ不能使用任何数据结构，全部都要自己写。
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 | #include<iostream> #include<string> #include<algorithm> #include<queue> using namespace std; struct status{ int arr[9]; }; string s_result; template <typename T> struct node{ T data; node<T> * next; }; template <typename T> struct list{ node<T> * head; int _size; list(){ _size = 0; head = NULL; } ~list(){ node <T> * current = head; node <T> * next; while (current != NULL){ next = current->next; delete current; current = next; } } void insert(T & data){ _size++; node<T> * ptr = new node<T>; ptr->data = data; ptr->next = head; head = ptr; } bool search(T & target){ node<T> * ptr = head; while (ptr != NULL){ if (ptr->data == target)return true; ptr = ptr->next; } return false; } }; list<int> hashtable[50021]; inline int h(const int m){ return (2 * m + 29) % 50021; } inline int status2int(status m){ int t = 0; for (int i = 1; i <= 8; i++){ t *= 10; t += m.arr[i]; } return t; } inline status int2status(int t){ status m; for (int i = 8; i >= 1; i--){ m.arr[i] = t % 10; t /= 10; } return m; } inline int change(int status_m, char type){ status m = int2status(status_m); int t; switch (type){ case 'A': swap(m.arr[1], m.arr[8]); swap(m.arr[2], m.arr[7]); swap(m.arr[3], m.arr[6]); swap(m.arr[4], m.arr[5]); break; case 'B': t = m.arr[4]; for (int i = 4; i >= 2; i--)m.arr[i] = m.arr[i - 1]; m.arr[1] = t; t = m.arr[5]; for (int i = 5; i <= 7; i++)m.arr[i] = m.arr[i + 1]; m.arr[8] = t; break; case 'C': t = m.arr[2]; m.arr[2] = m.arr[7]; m.arr[7] = m.arr[6]; m.arr[6] = m.arr[3]; m.arr[3] = t; break; } return status2int(m); } int BFS(int m){ queue<int> q; queue<int> qi; queue<string> qs; q.push(12345678); qi.push(0); qs.push(""); while (!q.empty()){ int t = q.front(); q.pop(); int time = qi.front(); qi.pop(); string str = qs.front(); qs.pop(); if (t == m){ s_result = str; return time; } else if (time > 30){ continue; } else{ int s = change(t, 'A'); if (!hashtable[h(s)].search(s)){ hashtable[h(s)].insert(s); q.push(s); qi.push(time + 1); qs.push(str + 'A'); } s = change(t, 'B'); if (!hashtable[h(s)].search(s)){ hashtable[h(s)].insert(s); q.push(s); qi.push(time + 1); qs.push(str + 'B'); } s = change(t, 'C'); if (!hashtable[h(s)].search(s)){ hashtable[h(s)].insert(s); q.push(s); qi.push(time + 1); qs.push(str + 'C'); } } } return -1; } int main(){ ios::sync_with_stdio(false); status m; for (int i = 1; i <= 8; i++){ cin >> m.arr[i]; } cout << BFS(status2int(m)) << endl; cout << s_result << endl; } |