程式碼備份區

題意：

有個有很多珠子的遊戲，可以轉左邊/右邊/全部，然後順時針/逆時針轉

問說起始狀態轉到某個狀態需要幾步

題目有說會在20步內

解法：

做雙向BFS；先把從起始狀態走10部內的狀態都建好，之後從終點狀態走，看有沒有撞到從起點開始走的狀態

有的話就把兩邊步數相加就是答案

程式碼：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define HASH_SIZE 1234567
#define QUEUE_SIZE 3378183

struct Hash{
    long long int state;
    char step;
    struct Hash *next;
}h[HASH_SIZE],h2[HASH_SIZE],*q[QUEUE_SIZE+10];
int qNum;

void initialHashTable(struct Hash h[]){
    int i;
    struct Hash *cur,*tmp;
    for(i=0;i<HASH_SIZE;++i){
        cur = h[i].next;
        while(cur!=NULL){
            tmp = cur;
            cur = cur->next;
            free(tmp);
        }
        h[i].next = NULL;
    }
}

#define hashFun(key)(key%HASH_SIZE)
/*
int hashFun(long long int key){
    return key % HASH_SIZE;
}
*/
long long int stateToKey(char state[]){
    int i;
    long long int num=0;
    for(i=0;i<12;++i){
        num = num*13+state[i];
    }
    return num;
}
void keyToState(long long int key,char state[]){
    int i;
    for(i=0;i<12;++i){
        state[11-i] = key%13;
        key/=13;
    }
    state[12] = '\0';
}
struct Hash* search(struct Hash h[],char state[]){
    long long int key = stateToKey(state);
    struct Hash *cur = h[hashFun(key)].next;
    while(cur != NULL && cur->state!=key){
        cur = cur->next;
    }
    return cur;
}

struct Hash* insert(struct Hash h[],char state[],int step){
    long long int key = stateToKey(state);
    struct Hash *head = &h[hashFun(key)];
    struct Hash *cur = (struct Hash *)malloc(sizeof(struct Hash));
    cur->state = key;
    cur->step = step;
    cur->next = head->next;
    head->next = cur;
    return cur;
}

void input(char state[]){
    int i;
    int num;
    for(i=0;i<12;++i){
        scanf("%d",&num);
        state[i] = (char)(num);
    }
    state[12] = '\0';
}
void turnAllC(char state[],char next[]){
    next[0] = state[1];
    next[1] = state[2];
    next[2] = state[3];
    next[3] = state[4];
    next[4] = state[5];
    next[5] = state[6];
    next[6] = state[7];
    next[7] = state[8];
    next[8] = state[9];
    next[9] = state[10];
    next[10] = state[11];
    next[11] = state[0];
}
void turnAllCC(char state[],char next[]){
    next[0] = state[11];
    next[1] = state[0];
    next[2] = state[1];
    next[3] = state[2];
    next[4] = state[3];
    next[5] = state[4];
    next[6] = state[5];
    next[7] = state[6];
    next[8] = state[7];
    next[9] = state[8];
    next[10] = state[9];
    next[11] = state[10];
}
void turnRightC(char state[],char next[]){
    next[11] = state[5];
    next[10] = state[11];
    next[9] = state[10];
    next[8] = state[9];
    next[7] = state[8];
    next[6] = state[7];
    next[5] = state[6];
    next[4] = state[4];
    next[3] = state[3];
    next[2] = state[2];
    next[1] = state[1];
    next[0] = state[0];
}
void turnRightCC(char state[],char next[]){
    next[11] = state[10];
    next[10] = state[9];
    next[9] = state[8];
    next[8] = state[7];
    next[7] = state[6];
    next[6] = state[5];
    next[5] = state[11];
    next[4] = state[4];
    next[3] = state[3];
    next[2] = state[2];
    next[1] = state[1];
    next[0] = state[0];
}
void turnLeftC(char state[],char next[]){
    next[0] = state[1];
    next[1] = state[2];
    next[2] = state[3];
    next[3] = state[4];
    next[4] = state[5];
    next[5] = state[11];
    next[6] = state[6];
    next[7] = state[7];
    next[8] = state[8];
    next[9] = state[9];
    next[10] = state[10];
    next[11] = state[0];
}
void turnLeftCC(char state[],char next[]){
    next[0] = state[11];
    next[1] = state[0];
    next[2] = state[1];
    next[3] = state[2];
    next[4] = state[3];
    next[5] = state[4];
    next[6] = state[6];
    next[7] = state[7];
    next[8] = state[8];
    next[9] = state[9];
    next[10] = state[10];
    next[11] = state[5];
}

void printState(char state[]){
    int i;
    for(i=0;state[i]!='\0';++i)printf("%d ",state[i]);
    puts("");
}
void (*transF[6])(char*,char*)={turnAllC,turnAllCC,turnRightC,turnRightCC,turnLeftC,turnLeftCC};

void initialBFS(char state[]){
    int i,j;
    char next[13];
    initialHashTable(h);
    state[12] = '\0';
    q[0] = insert(h,state,0);
    qNum = 1;
    for(i=0;q[i]->step<10;++i){
        keyToState(q[i]->state,state);
        for(j=0;j<6;++j){
            transF[j](state,next);
            if(search(h,next)==NULL){
                q[qNum++] = insert(h,next,q[i]->step+1);
            }
        }
    }
}
int BFS(char state[]){
    int i,j;
    struct Hash *cur;
    char next[13];
    initialHashTable(h2);
    state[12] = '\0';
    if((cur=search(h,state))!=NULL){
        return cur->step;
    }else {
        q[0] = insert(h2,state,-1);
    }
    qNum = 1;
    for(i=0;i<qNum;++i){
        keyToState(q[i]->state,state);
        for(j=0;j<6;++j){
            transF[j](state,next);
            if((cur=search(h,next))!=NULL){
                return cur->step - q[i]->step;
            }else if((cur=search(h2,next))==NULL){
                q[qNum++] = insert(h2,next,q[i]->step-1);
            }
        }
    }
    return -1;
}
int main(){
    int t;
    char state[13]={1,2,3,4,5,6,7,8,9,10,11,12,'\0'};
    memset(h,0,sizeof(h));
    memset(h2,0,sizeof(h2));
    initialBFS(state);
    scanf("%d",&t);
    while(t--){
        input(state);
        printf("%d\n",BFS(state));
    }
    return 0;
}