始终在800ms左右徘徊,唉!和书上的0.08差了10倍!难道是自己的hash函数有问题,做了个辅助键,还是不行!
怎么呢?细节还是有问题,状态的标示开的数组太大了,对性能影响太大了,失败的很!
等下在书上标注下!
 
还是很迷惑,不过主要问题是没有找到一个比较好的方法来去掉,path指针,为了省掉BFS的队列,又要增加状态的储存栈,实在是两者不可
兼得呀!还是有问题,我要疯了,昨晚写着写着Vista直接蓝屏了,搜索太容易爆栈了!
还是内力不过,加油写代码!
 
要点:
1.hash表的储存,hKey是一个辅助键,可以屏蔽掉一些明显不等的键值;[char的空间储存可以比int小很多,可惜没能找到一个比较好的映射函数,如果能找到一个
单射函数,那就爽了,根本不用memcmp比较了,失败!]
2.反向搜索的路径和正向搜索的路径是对称的,因此一定要在反向搜索时,把搜索路径转化到正向路径上
3.谁能告诉我,如果把hash表里面的路径空间再节省点,估算了下20MB,完全拿不上台面!不管了,下一个课题了!
 
时间:800MS[gcc]
/*
*ACM/ICPC Regional Contest : Spain
*Perimeter search algorithm
*/
#include <iostream>
#include <fstream>
#include <memory>
#define debug
#undef debug
using namespace std;
//Hashtable macro
//Hashtable pre-defined macro
const int NUMOFKEY=24, HSIZE=6007, MUL=5, MAX=17,//take care of hash overflow
    BACKHEIGHT=9,
    MAXBUF=10000000,MAXPATH=10000000,//20000000->20MB
    HALF=NUMOFKEY/2;
char input[NUMOFKEY], cmd[MAX], bestcmd[MAX];
char t[NUMOFKEY]={0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0,1,2,1};//final status
char buf[MAXBUF],pat[MAXPATH];
int backcmd[5]={0,3,4,1,2};//ignore the 0
int i_gK=0,i_gP=0,bestlen;
 
typedef struct node{
    __int64 key;//3key->64
    char *value, *path;//64
    int h;node* next;//64
}node;
typedef node* nodeptr;
nodeptr hash[HSIZE];//take care of bugs,6000*6->36K
//insert:bool-true,false;
bool insert(char* value, char* path, int h){//Key must be terminated!
    if(!value||!path) return false;
    //Hash key
    unsigned __int64 hKey=0;
    int hEntry=0, keycmd=-1;
    //char may be terminate
    for(int i=0; i<NUMOFKEY-3; i++) hKey=hKey*MUL+value[i];
    hEntry=hKey%HSIZE;
    #ifdef debug
    assert(hEntry>=0&&hEntry<HSIZE);
    #endif
    nodeptr nd=hash[hEntry], newnode, pre=NULL;//current node and pre
    for(;nd;pre=nd,nd=nd->next){
        if(nd->key!=hKey) continue;
        keycmd=memcmp(nd->value, value, NUMOFKEY-3);
        if(keycmd) continue;
        else break;//memcmp==0
    }
    //node==NULL||node->key>=hKey
    if(nd!=NULL&&!keycmd){
        if(h<nd->h){nd->h=h; nd->path=path; return true;}
        else if(h==nd->h) return true;
        else return false;
    }
    //one time for construction
    newnode=new node;
    newnode->key=hKey,newnode->value=value,newnode->path=path,newnode->h=h, newnode->next=NULL;
    if(!nd){//node==NULL
        if(!pre) hash[hEntry]=newnode;
        else pre->next=newnode;
    }
    else{//node!=NULL,
        if(!pre) hash[hEntry]=newnode;
        else pre->next=newnode;
        newnode->next=nd;
    }
    return true;
}
//nodeptr is required to return, that is needed to decide how to add path!
nodeptr search(char* value){
    if(!value) return NULL;
    unsigned __int64 hKey=0;
    int hEntry=0;
    for(int i=0;i<NUMOFKEY-3;i++) hKey=hKey*MUL+value[i];
    #ifdef debug
    assert(hKey>=0);
    #endif
    hEntry=hKey%HSIZE;
    for(nodeptr nd=hash[hEntry]; nd; nd=nd->next){
        if(nd->key!=hKey) continue;//obvious, not equal
        if(!memcmp(nd->value, value, NUMOFKEY-3)) return nd;//lose of quality, sigh!
    }
    return NULL;
}
//reset all
void biBFS();
//reuse cmd[MAX] to record path, then use pat to record!take care of ending
void backdfs(char* value, int step);
void fordfs(char* value, int step);
void rotate_t(char* arr, int type);
void rotate_t(char* arr, int type){//这个函数看似复杂,实际上运行效率比较高,基本已经不用改了
    int i,j;
    if(type==1){//left wheel turn CLOCK-WISE
        for(i=0,j=HALF-1;i<=j;i++,j–){//[0…HALF-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j];arr[j]^=arr[i];arr[i]^=arr[j];
        }
        if(arr[0]!=arr[1])
            arr[0]^=arr[1];arr[1]^=arr[0];arr[0]^=arr[1];
        for(i=2, j=HALF-1;i<=j;i++,j–){
            if(arr[i]!=arr[j])
                arr[i]^=arr[j];arr[j]^=arr[i];arr[i]^=arr[j];
        }
        memcpy(arr+NUMOFKEY-3,arr+HALF-3,3);
    }
    else if(type==2){//right wheel turn CLCOK-WISE
        for(i=HALF,j=NUMOFKEY-1;i<=j;i++,j–){//[HALF…NUMOFKEY-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        if(arr[NUMOFKEY-1]!=arr[NUMOFKEY-2])
            arr[NUMOFKEY-1]^=arr[NUMOFKEY-2],arr[NUMOFKEY-2]^=arr[NUMOFKEY-1],arr[NUMOFKEY-1]^=arr[NUMOFKEY-2];
        for(i=HALF,j=NUMOFKEY-3;i<=j;i++,j–){
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        memcpy(arr+HALF-3,arr+NUMOFKEY-3,3);
    }
    else if(type==3){//left wheel turn COUNTER-CLOCK-WISE
        for(i=0,j=HALF-1;i<=j;i++,j–){//[0…HALF-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        if(arr[HALF-1]!=arr[HALF-2])
            arr[HALF-1]^=arr[HALF-2],arr[HALF-2]^=arr[HALF-1],arr[HALF-1]^=arr[HALF-2];
        for(i=0, j=HALF-3;i<=j;i++,j–){
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        memcpy(arr+NUMOFKEY-3,arr+HALF-3,3);
    }
    else if(type==4){//right wheel turn COUNTER-CLOCK-WISE
        for(i=HALF,j=NUMOFKEY-1;i<=j;i++,j–){//[HALF…NUMOFKEY-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        if(arr[HALF]!=arr[HALF+1])
            arr[HALF]^=arr[HALF+1],arr[HALF+1]^=arr[HALF],arr[HALF]^=arr[HALF+1];
        for(i=HALF+2,j=NUMOFKEY-1;i<=j;i++,j–){
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        memcpy(arr+HALF-3,arr+NUMOFKEY-3,3);
    }
}
void backdfs(char* value, int step){
    if(step>BACKHEIGHT) return;
    int cur,cup;
    for(int i=1;i<5;i++){//cmd for height
        cmd[step]=backcmd[i];//here:command for back-rotated
        cur=i_gK,cup=i_gP,i_gK+=NUMOFKEY,i_gP+=step+1;//buf[i_gK…NUMOFKEY],pat[i_gP…BACKHEIGHT+1]
        #ifdef debug
        assert(i_gK<MAXBUF&&i_gP<MAXPATH);
        #endif
        memcpy(buf+cur,value,NUMOFKEY);
        memcpy(pat+cup,cmd,step+1);//[0…step],step+1 items
        rotate_t(buf+cur, i);
        if(insert(buf+cur, pat+cup, step))
            backdfs(buf+cur, step+1);
        else i_gK-=NUMOFKEY,i_gP-=(step+1);//move back,对于dirty state要毫不留情,只要不放入hash,一概复用!
    }
}
void fordfs(char* value, int step){
    if(step>bestlen-BACKHEIGHT) return;//cut-off half of branch
    nodeptr cur=search(value);
    if(!cur){
        for(int i=1; i<5; i++){
            cmd[step]=i;
            rotate_t(value, i);
            fordfs(value, step+1);
            rotate_t(value, backcmd[i]);//DFS的代码模板,不说什么了!
        }
    }
    else{//cur already exists for backdfs,cur->path[0,cur->h] back_table
        if(cur->h+1+step<bestlen){//back table[0…cur->h], however, fordfs?->0…step-1
            bestlen=cur->h+step+1;
            memcpy(bestcmd, cmd, step);
            for(int i=step,j=cur->h;j>-1;i++,j–) bestcmd[i]=cur->path[j];
        }
    }
}
void biBFS(){
    if(!memcmp(input, t, NUMOFKEY))//same
        cout<<"PUZZLE ALREADY SOLVED"<<endl;
    else{
        bestlen=17;
        fordfs(input, 0);
        if(bestlen>=17)
            cout<<"NO SOLUTION WAS FOUND IN 16 STEPS"<<endl;
        else{//out for best
            for(int i=0; i<bestlen; i++)
                if(bestcmd[i]!=0) cout<<(int)(bestcmd[i])<<" ";
            cout<<endl;
        }
    }
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in){
        cerr<<"error to open input.txt"<<endl;
        return EXIT_FAILURE;
    }
    cin.rdbuf(in.rdbuf());
    #endif
    int n,i=0,k;
    cin>>n;
    backdfs(t, 0);//search back for one time,由于从一个终结状态出发,因此我只需要做一个公共的hash表就可以了,9路长时,速度最快,和书上差不多,估计我的系统高速缓存相关,要比书上大一个级别
    while(n>0){
        for(i=0;i<NUMOFKEY;i++){ cin>>k, input[i]=k;}
        cout<<endl;
        biBFS();
        n–;
    }
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
Advertisements