ac代码:
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<queue> #include<map> using namespace std; typedef struct { int now[2][4]; string road; }NODE; map<int ,string>hash; queue<NODE>q; NODE xin ,tou; bool jhs(NODE a) { int temp = 1 ,sum = 0; for(int i = 0 ;i < 2 ;i ) for(int j = 0 ;j < 4 ;j ) { sum = temp * a.now[i][j]; temp *= 10; } if(hash[sum] != "") return 1; hash[sum] = a.road; return 0; } void DB_BFS() { int temp = 0; for(int i = 0 ;i < 4 ;i ) xin.now[0][i] = temp; for(int i = 3 ;i >= 0 ;i --) xin.now[1][i] = temp; xin.road = ""; hash.clear(); jhs(xin); while(!q.empty()) q.pop(); q.push(xin); int i ,j; while(!q.empty()) { tou = q.front(); q.pop(); for(i = 0 ;i < 2 ;i ) for(j = 0 ;j < 4 ;j ) { if(!i) xin.now[1][j] = tou.now[i][j]; else xin.now[0][j] = tou.now[i][j]; } xin.road = tou.road 'A'; if(!jhs(xin)) { q.push(xin); } for(i = 0 ;i < 2 ;i ) for(j = 1 ;j < 4 ;j ) xin.now[i][j] = tou.now[i][j-1]; xin.now[0][0] = tou.now[0][3]; xin.now[1][0] = tou.now[1][3]; xin.road = tou.road 'B'; if(!jhs(xin)) { q.push(xin); } xin = tou; xin.now[0][1] = tou.now[1][1]; xin.now[0][2] = tou.now[0][1]; xin.now[1][2] = tou.now[0][2]; xin.now[1][1] = tou.now[1][2]; xin.road = tou.road 'C'; if(!jhs(xin)) { q.push(xin); } } } int main () { char str1[20] ,str2[20]; int i ,j; &bsp; int X[20]; DB_BFS(); while(~scanf("%s%s" ,str1 ,str2)) { int temp = 0; for(i = 0 ;i < 4 ;i ++) X[str1[i] - 48] = ++ temp; for(i = 3 ;i >= 0 ;i --) X[str1[7 - i] - 48] = ++ temp; temp = 0; int tt = 1 ,sum = 0; for(i = 0 ;i < 4 ;i ++) { sum += X[str2[i] - 48] * tt; tt *= 10; } for(i = 7 ;i >= 4 ;i --) { sum += X[str2[i] - 48] * tt; tt *= 10; } if(hash[sum] == "AA") puts(""); else cout<<hash[sum]<<endl; } return 0; }