memcpy(next+12, origin+12, sizeof(int)*9);
next[21]=origin[7], next[22] = origin[8], next[23] = origin[9];
}
else if(dir==2){ // 右盘顺时针转
memcpy(next+12, origin+14, sizeof(int)*10);
next[22] = origin[12], next[23] = origin[13];
memcpy(next, origin, sizeof(int)*9);
next[9] = next[21], next[10] = next[22], next[11] = next[23];
}
else if(dir==3){ // 左盘逆时针转
memcpy(next, origin+2, sizeof(int)*10);
next[10] = origin[0], next[11] = origin[1];
memcpy(next+12, origin+12, sizeof(int)*9);
next[21]=next[9], next[22]=next[10], next[23]=next[11];
}
else if(dir==4){ // 右盘逆时针转
next[12] = origin[22], next[13] = origin[23];
memcpy(next+14, origin+12, sizeof(int)*10);
memcpy(next, origin, sizeof(int)*9);
next[9] = next[21], next[10] = next[22], next[11] = next[23];
}
}
// 把状态转换成字符串
inline string change_state(State &s){
string str;
for(int i=0; i<24; ++i)
str += s[i]+'0';
return str;
}
inline int try_to_insert(int s){
string str = change_state(que[s]);
if(!vis[str]){
vis[str]=1;
return true;
}
return false;
}
inline int back_try_to_insert(int s){
string str = change_state(que[s]);
if(!back_vis[str]){
back_vis[str]=s; //保存在队列在队列中的位置，而不是1或者true,方便后面输出路径
return true;
}
return false;
}
bool back_bfs(){ //逆向搜索
memset(back_father, 0, sizeof(back_father));
step[0] = step[1] = 0;
back_vis.clear();
back_vis[change_state(goal)] = 1;
int front=0, rear=1;
memcpy(que[0], goal, sizeof(goal));
while(front < rear){
State &s = que[front];
++front; continue;
}
for(int i=1; i<=4; ++i){
State &next = que[rear];
rotate(next, s, i);
step[rear] = step[front]+1;
if(back_try_to_insert(rear)){
back_father[rear] = front;
switch(i){ // 因为是逆向搜索，所以方向保存的也要是相反的
case 1:back_path[rear] = 3;break;
case 2:back_path[rear] = 4;break;
case 3:back_path[rear] = 1;break;
case 4:back_path[rear] = 2;break;
}
rear++;
}
}
++front;
}
return false;
}
bool bfs(){ // 正向搜索
memset(father, 0, sizeof(father));
step[0] = 0;
vis.clear();
vis[change_state(start)] = 1;
int front=0, rear=1;
memcpy(que[0], start, sizeof(start));
while(front < rear){
State &s = que[front];
if(step[front] > 8) {++front; continue;}
if(memcmp(s, goal, sizeof(goal))==0){
ans = front;
return false;
}
if(back_vis[change_state(s)]){
ans = front;
return true;
}
for(int i=1; i<=4; ++i){
State &next = que[rear];
rotate(next, s, i);
step[rear] = step[front]+1;
if(try_to_insert(rear)){
father[rear]=front; path[rear]=i;
rear++;
}
}
++front;
}
ans = -1;
}
void print_path(int cur){ // 打印出正向搜索部分
if(