八数码问题（暴力）

短命女 2021-12-15 12:29 212阅读 0赞

紫书上的程序真是牛逼

用到了路径寻找之类，还有状态数组，bfs，按坐标寻路的数组。hash，编码解码。STL等

#include<cstdio>
    #include<cstring>
    #include<set>
    #include<set>
    using namespace std;
    #define maxstate 1000000
    typedef int State[9];
    State st[maxstate] , goal;
    int dist[maxstate];
    
    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    
    const int hashsize = 1000003;
    int head[hashsize], next[maxstate];
    void init_lookup_table()  { memset(head,0,sizeof(head)); }
    int hash(State& s){
        int v=0;
        for(int i=0;i<9;i++) v=v*10+s[i];
        return v%hashsize;
    }
    int try_to_insert(int s){
        int h=hash(st[s]);
        int u=head[h];
        while(u){
            if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
            u=next[u];
        }
        next[s]=head[h];
        head[h]=s;
        return 1;
    }
    
    /*set<int> vis;
    void init_lookup_table() { vis.clear(); }
    int try_to_insert(int s){
        int v=0;
        for(int i=0;i<9;i++)  v =v*10 + st[s][i];
        if(vis.count(v)) return 0;
        vis.insert(v);
        return 1;
    }
    */
    /*
    int vis[362880], fact[9];
    void init_lookup_table(){
        fact[0]=1;
        for(int i=1;i<9;i++) fact[i]=fact[i-1]*i;
    }
    
    int try_to_insert(int s){
        int code = 0;
        for(int i=0;i<9;i++){
            int cnt=0;
            for(int j=i+1;j<9;j++) if(st[s][j] < st[s][i]) cnt++;
            code += fact[8-i]*cnt;
    
        }
        if(vis[code]) return 0;
        return vis[code]=1;
    }
    */
    /*
    
    2 6 4 1 3 7 0 5 8
    8 1 5 7 3 6 4 0 2
    */
    int bfs(){
        init_lookup_table();
        int front=1,rear=2;
        while(front < rear){
            State &s = st[front];
            if( memcmp(goal, s, sizeof(s))==0 ) return front;
            int z;
            for(z=0;z<9;z++) if(!s[z]) break;
            int x=z/3,y=z%3;
    //        printf("z=%d x=%d y=%d\n",z,x,y);
            for(int d=0;d<4;d++){
    
                int newx = x + dx[d];
                int newy = y + dy[d];
                int newz = newx*3 + newy;
    
                if(newx >= 0 && newx <=2 && newy>=0 && newy <=2)
                {
    
                    State& t = st[rear];
                    memcpy(&t,&s,sizeof(s));
                    t[newz] = s[z];
                    t[z]=s[newz];
                    dist[rear] = dist[front] + 1;
                    if(try_to_insert(rear)) {   rear++; }
                }
    
            }
            front++;
        }
        return 0;
    }
    
    int main()
    {
        for(int i=0;i<9;i++) scanf("%d", &st[1][i]);
        for(int i=0;i<9;i++) scanf("%d", &goal[i]);
        int ans = bfs();
    //    printf("%d\n",ans);
        if(ans > 0 ) printf("%d\n",dist[ans]);
        else printf("-1\n");
        return 0;
    }

转载于:https://www.cnblogs.com/yutingliuyl/p/7000726.html