学步园

大概思路跟1150的一样，数据量大了，我刚开始是用set<string>来存已经变换过的魔板，结果TLE，后来网上查了一下，用康托，结果WA。。但是我又不知道错在哪。最后用set<int>来存，AC了哦

/*<br /> * 1150.cpp<br /> *<br /> * Created on: Dec 18, 2010<br /> * Author: alfred<br /> */<br /> #include <queue><br /> #include <string><br /> #include <cstring><br /> #include <iostream><br /> #include <set><br /> using namespace std;<br /> struct step {<br /> int status[8];<br /> string step;<br /> };<br /> int target[8];<br /> const int init[8] = {1, 2, 3, 4, 8, 7, 6, 5};<br /> int maxStep;<br /> set<long> s;<br /> //bool isUsed[50000];<br /> //int fac[8];<br /> //<br /> //void setFac() {<br /> // fac[0] = fac[1] = 1;<br /> // for(int i = 2; i < 8; i++) {<br /> // fac[i] = fac[i - 1] * i;<br /> // }<br /> //}<br /> //int getID(int* tar) {<br /> // bool used[8];<br /> // memset(used, false, sizeof(used));<br /> // int id = 0;<br /> // for(int i = 0; i < 8; i++) {<br /> // for(int j = 1; j < tar[i]; j++) {<br /> // if(!used[j]) id += fac[7 - i];<br /> // }<br /> // used[tar[i] - 1] = true;<br /> // }<br /> // return id;<br /> //}<br /> long getID(int* tar) {<br /> return tar[7] * 1 + tar[6] * 10 + tar[5] * 100 + tar[4] * 1000 + tar[3] * 10000 + tar[2] * 100000 + tar[1] * 1000000 + tar[0] * 10000000;<br /> }<br /> void A(queue<step>& q, const step& statu) {<br /> step tmp;<br /> for(int i = 0; i < 4; i++) {<br /> tmp.status[i] = statu.status[i + 4];<br /> tmp.status[i + 4] = statu.status[i];<br /> }<br /> tmp.step = statu.step + 'A';<br /> long id = getID(tmp.status);<br /> if(s.find(id) == s.end()) {<br /> q.push(tmp);<br /> // isUsed[id] = true;<br /> s.insert(id);<br /> }<br /> }<br /> void B(queue<step>& q, const step& statu) {<br /> step tmp;<br /> for(int i = 1; i < 4; i++) {<br /> tmp.status[i] = statu.status[i - 1];<br /> tmp.status[i + 4] = statu.status[i - 1 + 4];<br /> }<br /> tmp.status[0] = statu.status[3];<br /> tmp.status[4] = statu.status[7];<br /> tmp.step = statu.step + 'B';<br /> long id = getID(tmp.status);<br /> if(s.find(id) == s.end()) {<br /> q.push(tmp);<br /> // isUsed[id] = true;<br /> s.insert(id);<br /> }<br /> }<br /> void C(queue<step>& q, const step& statu) {<br /> step tmp;<br /> tmp.status[0] = statu.status[0];<br /> tmp.status[1] = statu.status[5];<br /> tmp.status[2] = statu.status[1];<br /> tmp.status[3] = statu.status[3];<br /> tmp.status[4] = statu.status[4];<br /> tmp.status[5] = statu.status[6];<br /> tmp.status[6] = statu.status[2];<br /> tmp.status[7] = statu.status[7];<br /> tmp.step = statu.step + 'C';<br /> long id = getID(tmp.status);<br /> if(s.find(id) == s.end()) {<br /> q.push(tmp);<br /> // isUsed[id] = true;<br /> s.insert(id);<br /> }<br /> }<br /> void bfs() {<br /> s.clear();<br /> // memset(isUsed, false, sizeof(isUsed));<br /> queue<step> q;<br /> step tmp;<br /> memcpy(tmp.status, init, sizeof(init));<br /> q.push(tmp);<br /> long id = getID(tmp.status);<br /> // isUsed[id] = true;<br /> s.insert(id);<br /> while(!q.empty()) {<br /> tmp = q.front();<br /> q.pop();<br /> if(memcmp(tmp.status, target, sizeof(target)) == 0) {<br /> cout << tmp.step.size() << " " << tmp.step << endl;<br /> return;<br /> }<br /> if(tmp.step.size() == maxStep) {<br /> continue;<br /> }<br /> A(q, tmp);<br /> B(q, tmp);<br /> C(q, tmp);<br /> }<br /> cout << -1 << endl;<br /> }<br /> int main() {<br /> // setFac();<br /> cin >> maxStep;<br /> while(maxStep != -1) {<br /> for(int i = 0; i < 8; i++) {<br /> cin >> target[i];<br /> }<br /> bfs();<br /> cin >> maxStep;<br /> }<br /> return 0;<br /> }<br />  

已换康托，0.22sec，不错。

#include <iostream><br /> #include <string><br /> #include <queue><br /> #include <cstring><br /> using namespace std;<br /> struct node {<br /> int s[8];<br /> string step;<br /> };<br /> int maxStep;<br /> int init[8] = {1, 2, 3, 4, 8, 7, 6, 5};<br /> int tar[8];<br /> int fac[7];<br /> bool isUsed[50000];</p> <p>void setFac() {<br /> fac[0] = 1;<br /> for(int i = 2; i <= 7; i++) {<br /> fac[i - 1] = fac[i - 2] * i;<br /> }<br /> }<br /> int getID(int *data) {<br /> bool used[8];<br /> memset(used, false, sizeof(used));<br /> int id = 0;<br /> for(int i = 0; i < 8; i++) {<br /> for(int j = 1; j < data[i]; j++) {<br /> if(!used[j - 1])<br /> id += fac[6 - i];<br /> }<br /> used[data[i] - 1] = true;<br /> }<br /> return id;<br /> }<br /> void bfs() {<br /> memset(isUsed, false, sizeof(isUsed));<br /> queue<node> q;<br /> node _front;<br /> memcpy(_front.s, init, sizeof(init));<br /> _front.step = "";<br /> isUsed[getID(init)] = true;<br /> node _tmp;<br /> q.push(_front);<br /> int id;<br /> while(!q.empty()) {<br /> _front = q.front();<br /> q.pop();<br /> int step = _front.step.size();<br /> if(memcmp(_front.s, tar, sizeof(tar)) == 0) {<br /> cout << step << " "<br /> << _front.step << endl;<br /> return ;<br /> }<br /> if(step >= maxStep) continue;<br /> _tmp = _front;<br /> //A operator<br /> _tmp.s[0] = _front.s[4];<br /> _tmp.s[1] = _front.s[5];<br /> _tmp.s[2] = _front.s[6];<br /> _tmp.s[3] = _front.s[7];<br /> _tmp.s[4] = _front.s[0];<br /> _tmp.s[5] = _front.s[1];<br /> _tmp.s[6] = _front.s[2];<br /> _tmp.s[7] = _front.s[3];<br /> id = getID(_tmp.s);<br /> if(!isUsed[id]) {<br /> _tmp.step = _front.step + "A";<br /> q.push(_tmp);<br /> isUsed[id] = true;<br /> }<br /> //B operator<br /> _tmp.s[0] = _front.s[3];<br /> _tmp.s[1] = _front.s[0];<br /> _tmp.s[2] = _front.s[1];<br /> _tmp.s[3] = _front.s[2];<br /> _tmp.s[4] = _front.s[7];<br /> _tmp.s[5] = _front.s[4];<br /> _tmp.s[6] = _front.s[5];<br /> _tmp.s[7] = _front.s[6];<br /> id = getID(_tmp.s);<br /> if(!isUsed[id]) {<br /> _tmp.step = _front.step + "B";<br /> q.push(_tmp);<br /> isUsed[id] = true;<br /> }<br /> //C operator<br /> _tmp.s[0] = _front.s[0];<br /> _tmp.s[1] = _front.s[5];<br /> _tmp.s[2] = _front.s[1];<br /> _tmp.s[3] = _front.s[3];<br /> _tmp.s[4] = _front.s[4];<br /> _tmp.s[5] = _front.s[6];<br /> _tmp.s[6] = _front.s[2];<br /> _tmp.s[7] = _front.s[7];<br /> id = getID(_tmp.s);<br /> if(!isUsed[id]) {<br /> _tmp.step = _front.step + "C";<br /> q.push(_tmp);<br /> isUsed[id] = true;<br /> }<br /> }<br /> cout << -1 << endl;<br /> }<br /> int main() {<br /> int a;<br /> setFac();<br /> while(cin >> maxStep && maxStep != -1) {<br /> for(int i = 0; i < 8; i++) {<br /> cin >> tar[i];<br /> }<br /> bfs();<br /> }<br /> return 0;<br /> }