题解

120 条题解

  • 3
    @ 2018-03-13 21:47:15

    启发式搜索+康拓展开

    #include <iostream>
    #include <queue>
    #include <cmath>
    #include <cstring>
    using namespace std;
    
    char target[10] = "123804765";
    int target_hash;
    const int pos[][2]={{1,1},{0,0},{0,1},{0,2},{1,2},{2,2},{2,1},{2,0},{1,0}};
    bool vis[500000];
    int hashs[10];
    
    struct Node {
        int f,g,h;
        char c[10];
        friend bool operator < (const Node &a,const Node &b){
            if(a.f == b.f) return a.g < b.g;
            return a.f > b.f; 
        }
        
    };
    
    /*
    void print(const Node &n){
        cout<<"Node: "<<n.f<<" = "<<n.g<<" + "<<n.h<<endl;
        for(int i=0,j;i<3;i++){
            for(j=0;j<3;j++) 
                cout<<n.c[i*3+j]<<" ";
            
            cout<<endl;
        }
        cout<<endl;
    }
    */
    
    int unmatch(const char * c){
        int cnt = 0;
        for(int i=0,j;i<3;i++){
            for(j=0;j<3;j++){
                int p = c[i*3+j] - '0';
                if(p == 0) continue;
                //if(abs(pos[p][0] - i) || abs(pos[p][1] - j))
                //cnt+=1;
                cnt+=abs(pos[p][0] - i) + abs(pos[p][1] - j);
            }
        }
        return cnt;
    }
    
    int cantor(const char * c){
        int cnt=0,tmp;
        for(int i=0,k;i<9;i++){
            tmp = 0;
            for(k=i-1;k>=0;k--){
                if(c[k]>c[i]) tmp++;
            }
            cnt += hashs[i] * tmp;
        }
        return cnt;
    }
    
    bool up(char * c){
        int p0=-1;
        while(1){
            if(c[++p0] == '0') break;
        }
        if(p0>5) return false;
        c[p0] = c[p0+3];
        c[p0+3] = '0';
        return true;
    }
    
    bool down(char * c){
        int p0=-1;
        while(1){
            if(c[++p0] == '0') break;
        }
        if(p0<3) return false;
        c[p0] = c[p0-3];
        c[p0-3] = '0';
        return true;
    }
    
    bool left(char * c){
        int p0=-1;
        while(1){
            if(c[++p0] == '0') break;
        }
        if(p0%3 == 2) return false;
        c[p0] = c[p0+1];
        c[p0+1] = '0';
        return true;
    }
    
    bool right(char * c){
        int p0=-1;
        while(1){
            if(c[++p0] == '0') break;
        }
        if(p0%3 == 0) return false;
        c[p0] = c[p0-1];
        c[p0-1] = '0';
        return true;
    }
    
    int search(Node n){
        target_hash = cantor(target);
        if(cantor(n.c) == target_hash) return 0;
        vis[cantor(n.c)]=true;
        memset(vis,0,sizeof(vis));
        priority_queue<Node> que;
        que.push(n);
        while(!que.empty()){
            Node curr = que.top();
            que.pop();
        
            Node set[4];
            set[0]=set[1]=set[2]=set[3]=curr;
            up(set[0].c);left(set[1].c);down(set[2].c);right(set[3].c);
            for(int i=0;i<4;i++){
                set[i].g=curr.g+1;
                set[i].h=unmatch(set[i].c);
                set[i].f=set[i].g+set[i].h;
                int t = cantor(set[i].c);
                //cout<<i<<" "<<t<<":"<<endl;
                //print(set[i]);
                if(t == target_hash) return set[i].g;
                if(!vis[t]){
                    vis[t] = true;
                    que.push(set[i]);
                    //cout<<"pushed"<<endl<<endl;
                }
            }
        }
    }
    
    int main(){
        
        hashs[0]=1;
        for(int i=1;i<11;i++){
            hashs[i] = hashs[i-1] * i;
        }
        Node start;
        cin>>start.c;
        //strcpy(start.c,"203184765");
        start.g=0;
        start.h=unmatch(start.c);
        start.f=start.g+start.h;
        //print(start);
        cout<<search(start);
        return 0;
    } 
    
  • 1
    @ 2020-12-02 14:58:54

    简单的搜索题写这么久...我是真的菜

    
    #include <stdio.h>
    
    long queue[100000][2] = {0};
    const int goal[9] = {1, 2, 3, 8, 0, 4, 7, 6, 5};
    long goalLong;
    const short pInt[9][4] = {{1, 3, -1, -1},
                              {0, 2, 4,  -1},
                              {1, 5, -1, -1},
                              {0, 4, 6,  -1},
                              {1, 3, 5,  7},
                              {2, 4, 8,  -1},
                              {3, 7, -1, -1},
                              {6, 8, 4,  -1},
                              {5, 7, -1, -1}};
    long frac_array[10];
    
    long frac(int n) {
        if (n == 0) return 1;
        return frac_array[n] ? frac_array[n] : (frac_array[n] = n * frac(n - 1));
    }
    
    long cantor(const int *array, int n) {
        long answer = 0;
        for (int i = 0; i < n; i++) {
            int index = 0;
            for (int j = i + 1; j < n; j++)
                if (array[i] > array[j])index++;
            answer += frac(n - i - 1) * index;
        }
        return answer;
    }
    
    void revCantor(long expanded, int n, int array[n]) {
        int used[100] = {0};
        for (int i = 0; i < n; i++) {
            array[i] = expanded / frac(n - i - 1) + 1;
            for (int j = 0; j < n; j++) {
                if (used[j] == 0) {
                    array[i]--;
                    if (array[i] == 0) {
                        array[i] = j;
                        used[j] = 1;
                        break;
                    }
                }
            }
            expanded %= frac(n - i - 1);
        }
    }
    
    void swap(int *a, int *b) {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }
    
    char contain(long expanded, int tail) {
        for (int i = 0; i < tail - 1; i++) {
            if (expanded == queue[i][0]) {
                return 1;
            }
        }
        return 0;
    }
    
    /*
     * 0 1 2
     * 3 4 5
     * 6 7 8
     *
     * */
    int main() {
        int input_array[9];
        goalLong = cantor(goal, 9);
        revCantor(goalLong, 9, input_array);
        for (short i = 0; i < 9; i++) {
            input_array[i] = getchar() - '0';
    
        }
        queue[0][0] = cantor(input_array, 9);
        queue[0][1] = 0;
        if (queue[0][0] == goalLong) {
            putchar('0');
            return 0;
        }
        //宽度优先搜索
        int head = 0, tail = 1;
        while (head < tail) {
            int tmp_array[9] = {0};
            revCantor(queue[head][0], 9, tmp_array);
            int zeroIndex = 0;
            for (int i = 0; i < 9; i++) {
                if (tmp_array[i] == 0) {
                    zeroIndex = i;
                    break;
                }
            }
            //四方向扩展
            for (int i = 0; i < 4; i++) {
                if (pInt[zeroIndex][i] >= 0) {
                    swap(&tmp_array[zeroIndex], &tmp_array[pInt[zeroIndex][i]]);
    
                    long c = cantor(tmp_array, 9);
                    if (!contain(c, tail)) {
                        queue[tail][0] = c;
                        queue[tail][1] = queue[head][1] + 1;
                        if (queue[tail][0] == goalLong) {
                            printf("%ld", queue[tail][1]);
                            return 0;
                        }
                        tail++;
                    }
    
                    swap(&tmp_array[zeroIndex], &tmp_array[pInt[zeroIndex][i]]);
                }
            }
            head++;
        }
        return 0;
    }
    
    
  • 1
    @ 2020-07-22 17:14:31

    1.利用stirng来表示状态
    2.利用<unordered_map> 可以更容易地判断路径重复和记录距离
    3./x %x 来一维转二维

    #include <iostream>
    #include <algorithm>
    #include <unordered_map>
    #include <queue>
    
    using namespace std;
    
    int bfs(string state)
    {
        queue<string> q;
        unordered_map<string, int> d;
    
        q.push(state);
        d[state] = 0;
    
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
        string end = "123804765";
        while (q.size())
        {
            auto t = q.front();
            q.pop();
    
            if (t == end) return d[t];
    
            int distance = d[t];
            int k = t.find('0');
            int x = k / 3, y = k % 3;
            for (int i = 0; i < 4; i ++ )
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < 3 && b >= 0 && b < 3)
                {
                    swap(t[a * 3 + b], t[k]);
                    if (!d.count(t))
                    {
                        d[t] = distance + 1;
                        q.push(t);
                    }
                    swap(t[a * 3 + b], t[k]);
                }
            }
        }
    
        return -1;
    }
    
    int main()
    {
        string state;
        cin>>state;
    
        cout << bfs(state) << endl;
    
        return 0;
    }
    
  • 1
    @ 2017-12-16 23:11:06

    bfs一下

    #include<cstdio>
    #include<cstring>
    #include<set>
    using namespace std;
    
    typedef int State[9];
    const int MAXSTATE=1000000;
    State st[MAXSTATE],goal={1,2,3,8,0,4,7,6,5};
    int dist[MAXSTATE];
    
    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;
    }
    
    const int dx[]={-1,1,0,0};
    const int dy[]={0,0,-1,1};
    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;
            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<3 && newy>=0 && newy<3)
                {
                    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()
    {
        char s[15];
        scanf("%s",s);
        for(int i=0;i<9;i++)
            st[1][i]=s[i]-'0';
    //  for(int i=0;i<9;i++) printf(" %d ",st[1][i]); 
        int ans = bfs();
        printf("%d\n", dist[ans]);
        return 0;
    }
    
    
  • 0
    @ 2019-02-11 18:23:17

    第一次一次性AC,热泪盈眶

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    #include<vector>
    #include<queue>
    #include<map>
    using namespace std;
    int up(int i){
        if(i-3>=0) return i-3;
        else return -1;
    }
    int down(int i){
        if(i+3<9) return i+3;
        else return -1;
    }
    int left(int i){
        if(i%3==0) return -1;
        else return i-1;
    }
    int right(int i){
        if(i%3==2) return -1;
        else return i+1;
    }
    queue<string> q;
    map<string,int> s;
    string t="1238047654";
    int bfs(){
        int pos,z;
        string a,b;
        while(!q.empty()){
            a = q.front(); q.pop();
            z = a[9]-'0';
            if((pos=up(z))!=-1){
                b = a;
                swap(b[z],b[pos]);
                b[9] = pos+'0';
                if(!s.count(b)) s[b] = s[a]+1, q.push(b);
                if(b==t) return s[b];
            }
            if((pos=down(z))!=-1){
                b = a;
                swap(b[z],b[pos]);
                b[9] = pos+'0';
                if(!s.count(b)) s[b] = s[a]+1, q.push(b);
                if(b==t) return s[b];
            }
            if((pos=left(z))!=-1){
                b = a;
                swap(b[z],b[pos]);
                b[9] = pos+'0';
                if(!s.count(b)) s[b] = s[a]+1, q.push(b);
                if(b==t) return s[b];
            }
            if((pos=right(z))!=-1){
                b = a;
                swap(b[z],b[pos]);
                b[9] = pos+'0';
                if(!s.count(b)) s[b] = s[a]+1, q.push(b);
                if(b==t) return s[b];
            }
        }
    }
    int main()
    {
        string a;
        cin >> a;
        int z;
        for(int i=0; i<a.size();i++){
            if(a[i]=='0'){
                z = i;
                break;
            }
        }
        a += z+'0';
        q.push(a);
        s[a] = 0;
        cout << bfs();
        return 0;
    }
    
    
  • 0
    @ 2019-01-10 11:34:18

    #include<stdio.h>
    #include<stdlib.h>
    using namespace std;

    //算法思想:宽度优先搜索,从两头向中间接近,直到相遇
    //宽搜队列,每一个状态的节点

    struct node{
    short a[10];//状态
    short zero;//零点位置
    short fore; //上一步的操作
    short step; //搜索树层数(操作了多少步)
    node *next;
    };
    //题目中给出的移动方式,可以等效于零点向四个方向移动
    //依据x定出移动方向,对head节点中的零点做移动,存到tail节点中
    //x:1上;2,下;3,左;4,右
    void move(node *head, node *tail, short x)
    {
    int k,i;
    for(i=1;i<=9;i++)
    tail->a[i]=head->a[i];
    tail->zero=head->zero;
    tail->step=head->step+1;
    i=tail->zero;
    switch(x)
    {
    case 1:{
    tail->zero-=3;
    k=tail->a[i-3];
    tail->a[i-3]=tail->a[i];
    tail->a[i]=k;
    tail->fore=2;
    break;
    }
    case 2:{
    tail->zero+=3;
    k=tail->a[i+3];
    tail->a[i+3]=tail->a[i];
    tail->a[i]=k;
    tail->fore=1;
    break;
    }
    case 3:{
    tail->zero-=1;
    k=tail->a[i-1];
    tail->a[i-1]=tail->a[i];
    tail->a[i]=k;
    tail->fore=4;
    break;
    }
    case 4:{
    tail->zero+=1;
    k=tail->a[i+1];
    tail->a[i+1]=tail->a[i];
    tail->a[i]=k;
    tail->fore=3;
    break;
    }
    }
    }
    //判断零点在x,移动方向是y,能否移动(是否越界)

    bool movable(int x,int y)
    {
    switch(y)
    {
    case 1:{
    if(x<4) return 0;
    break;
    }
    case 2:{
    if(x>6) return 0;
    break;
    }
    case 3:{
    if(x%3==1) return 0;
    break;
    }
    case 4:{
    if(x%3==0) return 0;
    break;
    }
    }
    return 1;
    }
    //九进制hash函数
    //每个状态可以用一个九进制九位数来表示
    unsigned long hash(node *p)
    {
    int n,i;
    //最小的一状态,粗略记录为九进制下的012000000
    const int min_hash=63412811;
    n=0;
    for(i=1;i<=9;i++)
    {
    n=n*9;//九进制数,不断进位
    n+=p->a[i];
    }
    n-=min_hash;
    return n;
    }

    //二分查找树,a用于储存九进制表示的节点状态
    struct node2{
    unsigned long a;
    short step;
    node2 *left;
    node2 *right;
    };

    //在二分查找树中搜索一个节点,如果找到,返回1;没有找到则插入该节点并返回0
    bool search_insert(unsigned long a,node2 *head,short step)
    {
    node2 *p,*q;
    p=head;
    q=p;
    //大于该父节点则插入右分支,小于父节点则插入左分支。
    //寻找节点
    //step记录每个节点是经过了多少步的搜索
    while(q!=NULL)
    {
    p=q;
    if(a<p->a) q=p->left;
    if(a>p->a) q=p->right;
    if(a==p->a) return 1;
    }
    //插入节点
    if(a<p->a)
    {
    p->left=new node2;
    q=p->left;
    }
    if(a>p->a)
    {
    p->right=new node2;
    q=p->right;
    }
    q->a=a;
    q->step=step;
    q->left=NULL;
    q->right=NULL;
    return 0;
    }
    //在查找树中搜索一个节点。没找到返回0,找到则返回该节点经历了多少步搜索。
    short search(unsigned long a,node2 *head)
    {
    node2 *p,*q;
    short step;
    p=head;
    q=p;
    while(q!=NULL)
    {
    p=q;
    if(a<p->a) q=p->left;
    if(a>p->a) q=p->right;
    if(a==p->a)
    {
    step=p->step;
    return step;
    }
    }
    return 0;
    }
    //递归删除二叉查找树
    void release(node2 *p)
    {
    if(p->left!=NULL)
    release(p->left);
    if(p->right!=NULL)
    release(p->right);
    delete p;

    }

    int main()
    {
    //head1,tail1是从起点出发的宽搜队列;head2,tail2是从终点出发的宽搜队列。p是过渡用的变量
    node *head1,*tail1,*head2,*tail2,*p;
    int i,j,k;//循环变量
    //记录目前搜索到的状态值,l0是两棵搜索树相遇的位置

    unsigned long l,l0;
    char ch;
    //hash1,从起点开始搜索产生的查找树;hash2,从终点搜索产生的查找树。
    node2 *hash1, *hash2;
    //题目中所给的目标状态,a[0]=9纯粹是为了占位置。
    int a[10]={9,1,2,3,8,0,4,7,6,5};
    short b=0; //b=0 没有完成任务,b>0表示完成了任务
    short step; //用于记录步数,过渡用变量

    //初始情况,存入宽搜队列
    head1=new node;
    for(i=1;i<=9;i++)
    {
    scanf("%c",&ch);
    k=(short) (ch-'0');
    head1->a[i]=k;
    if(k==0) head1->zero=i;
    }
    head1->fore=0;
    head1->step=0;
    head1->next=NULL;
    tail1=head1;
    //初始情况加入查找树
    hash1=new node2;
    hash1->left=NULL;
    hash1->right=NULL;
    l=hash(head1);
    hash1->a=l;
    //目标节点存入宽搜队列
    head2=new node;
    for(i=1;i<=9;i++)
    head2->a[i]=a[i];
    head2->zero=5;
    head2->fore=0;
    head2->step=0;
    head2->next=NULL;
    tail2=head2;
    //目标节点加入查找树
    hash2=new node2;
    hash2->left=NULL;
    hash2->right=NULL;
    l=hash(head2);
    hash2->a=l;
    //先操作初始队列,后操作返回队列,最后判断是否相遇
    while(b==0)
    {
    //从前向后搜索
    //head节点上一步的反向操作,这一剪枝,以免进入死循环。
    k=(int) head1->fore;
    //head节点零点位置,用于判断移动方向
    j=(int) head1->zero;
    for(i=1;i<=4;i++)
    if((i!=k)&&(movable(j,i)==1))//可以移动
    {
    p=new node;
    move(head1,p,i);
    l=hash(p);
    step=p->step;
    if(search_insert(l,hash1,step)==1)
    delete p;
    else {
    tail1->next=p;
    tail1=p;
    p->next=NULL;
    }

    }
    //释放刚刚拓展过的节点
    p=head1;
    head1=head1->next;
    delete p;

    //从后向前搜索,步骤与从前向后搜索相同

    k=(int) head2->fore;
    j=(int) head2->zero;
    for(i=1;i<=4;i++)

    if((i!=k)&&(movable(j,i)==1))
    {
    p=new node;
    move(head2,p,i);
    l=hash(p);
    step=p->step;
    if(search_insert(l,hash2,step)==1)
    delete p;
    else

    {
    tail2->next=p;
    p->next=NULL;
    tail2=p;

    }
    b=search(l,hash1);
    if(b>0){
    l0=l;
    break;
    }

    }

    //释放搜索过的节点
    p=head2;
    head2=head2->next;
    delete p;
    }
    //从起点搜索了多少步,从终点搜索了多少步,相加即为总步数
    k=(int)search(l0,hash1)+(int)search(l0,hash2);
    printf("%d\n",k);
    //释放队列
    while(head1!=NULL)
    {
    p=head1;
    head1=head1->next;
    delete p;
    }
    while(head2!=NULL)
    {
    p=head2;
    head2=head2->next;
    delete p;
    }
    //释放查找树
    release(hash1);
    release(hash2);
    }

  • 0
    @ 2018-12-01 21:41:20
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <assert.h>
    #include <string.h>
    #include <ctype.h>
    #define max(a, b) (a > b ? a : b)
    #define MOD 100007
    #define MAX_SIZE 524288
    
    int adj[9][9] = {{0, 1, 0, 1, 0, 0, 0, 0, 0},
                     {1, 0, 1, 0, 1, 0, 0, 0, 0},
                     {0, 1, 0, 0, 0, 1, 0, 0, 0},
                     {1, 0, 0, 0, 1, 0, 1, 0, 0},
                     {0, 1, 0, 1, 0, 1, 0, 1, 0},
                     {0, 0, 1, 0, 1, 0, 0, 0, 1},
                     {0, 0, 0, 1, 0, 0, 0, 1, 0},
                     {0, 0, 0, 0, 1, 0, 1, 0, 1},
                     {0, 0, 0, 0, 0, 1, 0, 1, 0}};
    
    typedef struct item {
        int value;
        int step;
        int cost;
    }Item;
    
    typedef struct pq {
        Item *items;
        int nitems;
        int nspots;
    } *PQ, PQrep;
    
    typedef int KEYS; 
    
    typedef struct tree {
        struct tree *left, *right;
        KEYS value;
        int hi;
    } *BST, BSTrep;
    
    typedef struct maps {
        BST *keys;
        int nkeys;
    } *Maps, Maprep; 
    // the hashing ADT
    int searchKey(Maps h, KEYS value);
    BST newBSTnode(KEYS value);
    BST insertBST(BST t, KEYS value);
    void insertKey(Maps h, KEYS value);
    Maps newHash();
    int searchBST(BST t, KEYS value);
    int cmp(KEYS value1, KEYS value2);
    void dropMaps(Maps h);
    void dropBST(BST t);
    int height(BST t);
    BST rebalance(BST t);
    void showMaps(Maps h);
    // the priorityQueue ADT
    PQ newPQ(void);
    void insertPQ(PQ q, Item newitem);
    void floatup(PQ q, int index);
    int highpriority(Item v1, Item v2);
    void swap(PQ q, int index1, int index2);
    int qempty(PQ q);
    Item pop(PQ q);
    void floatdown(PQ q, int index);
    void showPQ(PQ q, int index, int depth);
    void freePQ(PQ q);
    // the A_star algrithum
    void A_Star(int, int);
    int hcost(int curr, int dest);
    
    int main() {
        int end;
        scanf("%d", &end);
        A_Star(123804765, end);
        return 0;
    }
    
    void A_Star(int start, int dest) {
        PQ q = newPQ();
        Maps h = newHash();
        Item newitem, nextitem;
        char *str, *tmp, tp; 
        int reachable[9], size, i, len, index;
        
        newitem.step = 0;
        newitem.value = start;
        newitem.cost = hcost(start, dest);
        insertPQ(q, newitem);
        while (!qempty(q)) {
            newitem = pop(q);
            
            if (newitem.value == dest) {
                printf("%d\n", newitem.step);
                return;
            }
            
            if (searchKey(h, newitem.value)) {
                continue;
            }
            
            insertKey(h, newitem.value);
            str = (char *) calloc(11, sizeof(char));
            tmp = (char *) calloc(11, sizeof(char));
            if (newitem.value < 1e8) {
                str[0] = '0';
                sprintf(tmp, "%d", newitem.value);
                strcat(str, tmp);
            } else {
                sprintf(str, "%d", newitem.value);
            }
            
            size = 0;
            len = strlen(str);
            
            for (i = 0 ; i < len; i++) {
                if (str[i] == '0') {
                    index = i;
                    break;
                }
            }
            
            for (i = 0 ; i < len; i++) {
                if (adj[i][index] == 1) {
                    strcpy(tmp, str);
                    tp = tmp[index];
                    tmp[index] = tmp[i];
                    tmp[i] = tp;
                    reachable[size++] = atoi(tmp);
                }
            }
            
            free(str);
            free(tmp);
            for (i = 0 ; i < size; i++) {
                if (!searchKey(h, reachable[i])) {
                    nextitem.value = reachable[i];
                    nextitem.step = 1 + newitem.step;
                    nextitem.cost = newitem.step + hcost(reachable[i], dest); 
                    insertPQ(q, nextitem);
                }
            }
            /*
                for value in reachable items and items not in hashing map {
                    nextitem.value = value;
                    nextitem.step = 1 + newitem.step;
                    nextitem.cost = newitem.step + hcost(value, dest); 
                    insertPQ(PQ, nextitem);
                } 
            */
        }
    }
    
    
    
    int hcost(int curr, int dest) {
        char *str1, *str2, *tmp;
        int count = 0, i;
        str1 = (char *) calloc(11, sizeof(char));
        str2 = (char *) calloc(11, sizeof(char));
        tmp = (char *) calloc(11, sizeof(char));
        if (curr < 1e8) {
            str1[0] = '0';
            sprintf(tmp, "%d", curr);
            strcat(str1, tmp);
        } else {
            sprintf(str1, "%d", curr);
        }
        free(tmp);
        tmp = (char *) calloc(11, sizeof(char));
        if (dest < 1e8) {
            str2[0] = '0';
            sprintf(tmp, "%d", dest);
            strcat(str2, tmp);
        } else {
            sprintf(str2, "%d", dest);
        }
        free(tmp);
        int len = strlen(str1);
        for (i = 0 ; i < len; i++) {
            if (str1[i] != str2[i]) count++;
        }
        
        free(str1);
        free(str2);
        return count;
    }
    
    Maps newHash() {
        Maps h = (Maps) calloc(1, sizeof(Maprep));
        h->nkeys = MOD;
        h->keys = (BST *) calloc(h->nkeys + 1, sizeof(BST));
        int i;
        for (i = 0 ; i < h->nkeys; i++) {
            h->keys[i] = NULL;
        }
        return h;
    }
    
    BST newBSTnode(KEYS value) {
        BST node = (BST) malloc(sizeof(BSTrep));
        node->left = NULL;
        node->right = NULL;
        node->value = value;
        node->hi = 0;
        return node;
    }
    
    int cmp(KEYS value1, KEYS value2) {
        if (value1 == value2) return 0;
        if (value1 < value2) return -1;
        return 1;
    }
    
    int searchBST(BST t, KEYS value) {
        if (t == NULL) return 0;
        if (cmp(t->value, value) == 0) return 1;
        if (cmp(t->value, value) == -1) return searchBST(t->right, value);
        return searchBST(t->left, value);
    }
    
    int searchKey(Maps h, KEYS value) {
        return searchBST(h->keys[value % MOD], value);
    }
    
    BST leftRotate(BST t) {
        if (t == NULL || t->right == NULL) return t;
        BST tmp = t->right;
        t->hi = max(height(t->left), height(tmp->left)) + 1;
        t->right = tmp->left;
        tmp->left = t;
        tmp->hi = max(height(tmp->left), height(tmp->right)) + 1;
        return tmp;
    }
    
    BST rightRotate(BST t) {
        if (t == NULL || t->left == NULL) return t;
        BST tmp = t->left;
        t->hi = max(height(t->right), height(tmp->right)) + 1;
        t->left = tmp->right;
        tmp->right = t;
        tmp->hi = max(height(tmp->right), height(tmp->left)) + 1;
        return tmp;
    }
    
    BST rebalance(BST t) {
        if (t == NULL) return t;
        if (height(t->left) - height(t->right) > 1) {
            if (height(t->left->left) > height(t->left->right)) {
                t = rightRotate(t);
            } else if(height(t->left->left) < height(t->left->right)) {
                t->left = leftRotate(t->left);
                t = rightRotate(t);
            }
        } else if (height(t->right) - height(t->left) > 1) {
            if (height(t->right->left) > height(t->right->right)) {
                t->right = rightRotate(t->right);
                t = leftRotate(t);
            } else if (height(t->right->left) < height(t->right->right)) {
                t = leftRotate(t);
            }
        }
        return t;
    }
    
    int height(BST t) {
        if (t == NULL) return -1;
        return t->hi;
    }
    
    BST insertBST(BST t, KEYS value) {
        if (t == NULL) return newBSTnode(value);
        if (cmp(t->value, value) == 0) return t;
        if (cmp(t->value, value) == -1) t->right = insertBST(t->right, value);
        else t->left = insertBST(t->left, value);
        t->hi = max(height(t->left), height(t->right)) + 1;
        t = rebalance(t);
        t->hi = max(height(t->left), height(t->right)) + 1;
        return t; 
    }
    
    void insertKey(Maps h, KEYS value) {
        h->keys[value % MOD] = insertBST(h->keys[value % MOD], value);
    }
    
    void dropBST(BST t) {
        if (t != NULL) {
            dropBST(t->left);
            dropBST(t->right);
            free(t);
        }
    }
    
    void dropMaps(Maps h) {
        int i;
        for (i = 0 ; i < h->nkeys; i++) {
            dropBST(h->keys[i]);
        }
        free(h);
    }
    
    void showBST(BST h, int level) {
        if (h == NULL) return;
        int i;
        showBST(h->right, level + 1);
        for (i = 0 ; i < level; i++) printf("\t\t");
        printf("%d\n", h->value);
        showBST(h->left, level + 1);
    }
    
    void showMaps(Maps h) {
        int i;
        for (i = 0 ; i < h->nkeys; i++) {
            if (h->keys[i] != NULL) {
                printf("the %dth key is\n", i);
                showBST(h->keys[i], 0);
                printf("\n");
            }
        }
    }
    
    
    void freePQ(PQ q) {
        free(q->items);
        free(q);
    }
    
    PQ newPQ() {
        PQ q = (PQ) calloc(1, sizeof(PQrep));
        q->items = (Item *) calloc(1 + MAX_SIZE, sizeof(Item));
        q->nspots = MAX_SIZE;
        q->nitems = 0;
        return q;
    }
    
    int highpriority(Item v1, Item v2) {
        return (v1.cost < v2.cost);
    }
    
    void swap(PQ q, int index1, int index2) {
        Item tmp;
        tmp = q->items[index1];
        q->items[index1] = q->items[index2];
        q->items[index2] = tmp;
    }
    
    void floatup(PQ q, int index) {
        if (index <= 1) return;
        if (highpriority(q->items[index], q->items[index / 2])) {
            swap(q, index, index / 2);
            floatup(q, index / 2);
        }
    }
    
    void insertPQ(PQ q, Item newitem) {
        if (q->nitems >= q->nspots) return;
        q->items[++q->nitems] = newitem;
        floatup(q, q->nitems);
    }
    
    int qempty(PQ q) {
        return (q->nitems <= 0);
    }
    
    void floatdown(PQ q, int index) {
        if (q->nitems  < index * 2 + 1) return;
        if (q->nitems >= 2 * index + 1) {
            if (highpriority(q->items[index * 2], q->items[index * 2 + 1])) {
                if (highpriority(q->items[index * 2], q->items[index])) {
                    swap(q, index * 2, index);
                    floatdown(q, index * 2);
                }
            } else {
                if (highpriority(q->items[index * 2 + 1], q->items[index])) {
                    swap(q, index * 2 + 1, index);
                    floatdown(q, index * 2 + 1);
                }
            }
        } else if (q->nitems >= 2 * index) {
            if (highpriority(q->items[index * 2], q->items[index])) {
                swap(q, index * 2, index);
                floatdown(q, index * 2);
            }
        }
    }
    
    Item pop(PQ q) {
        assert(q != NULL);
        assert(q->items != NULL);
        assert(!qempty(q));
        Item value = q->items[1];
        swap(q, 1, q->nitems);
        q->nitems--;
        floatdown(q, 1);
        return value;   
    }
    
    void showPQ(PQ q, int index, int depth) {
        assert(q != NULL);
        if (q->nitems < index) return;
        showPQ(q, index * 2 + 1, depth + 1);
        int i;
        for (i = 0 ; i < depth; i++) printf("\t\t");
        printf("%d\n", q->items[index].value);
        showPQ(q, index * 2, depth + 1);
    }
    
  • 0
    @ 2018-09-19 19:12:37

    方法一:BFS+队列式分支界限优化+STL节约空间

    #include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    #include <string>
    #include <map>
    #define INIT 400000
    using namespace std;
    
    struct eight
    {
        bool b;
        int sum;
        eight():b(false),sum(0)
        {
    
        }
    };
    int ans=INIT;
    map<string,eight> judge;
    queue<string> q;
    
    void BFS(const string& str)
    {
        string t;
        judge[str].b=true;
        q.push(str);
        while(q.empty()==false)
        {
            t=q.front();
            q.pop();
            if(t=="123804765")
                ans=min(ans,judge[t].sum);
            else if(judge[t].sum<ans)
            {
                int loc=t.find('0');
                int x=loc/3;
                int y=loc%3;
                int step=judge[t].sum;
                if(x-1>=0)
                {
                    swap(t[loc],t[loc-3]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        q.push(t);
                    }
                    swap(t[loc],t[loc-3]);
                }
                if(y-1>=0)
                {
                    swap(t[loc],t[loc-1]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        q.push(t);
                    }
                    swap(t[loc],t[loc-1]);
                }
                if(y+1<=2)
                {
                    swap(t[loc],t[loc+1]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        q.push(t);
                    }
                    swap(t[loc],t[loc+1]);
                }
                if(x+1<=2)
                {
                    swap(t[loc],t[loc+3]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        q.push(t);
                    }
                    swap(t[loc],t[loc+3]);
                }
            }
        }
    }
    
    int main()
    {
        string str;
        cin>>str;
        if(str=="123804765")
            cout<<0<<endl;
        else
            BFS(str);
        if(ans==INIT)
            cout<<-1<<endl;
        else
            cout<<ans<<endl;
        return 0;
    }
    

    方法二:BFS+A*+STL节约空间

    #include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    #include <string>
    #include <map>
    #define INIT 400000
    using namespace std;
    
    const string des="123804765";
    struct eight
    {
        bool b;
        int sum;
        int num;
        eight():b(false),sum(0),num(0)
        {
    
        }
    };
    int ans=INIT;
    map<string,eight> judge;
    struct cmp
    {
        bool operator () (const string& a,const string& b)
        {
            return judge[a].num>judge[b].num;
        }
    };
    priority_queue<string,vector<string>,cmp> q;
    
    void cal_num(const string& t)
    {
        int c=0;
        for(int i=0;i<9;i++)
            if(t[i]!=des[i])
                c++;
        judge[t].num=c+judge[t].sum;
    }
    
    void BFS(const string& str)
    {
        string t;
        judge[str].b=true;
        cal_num(str);
        q.push(str);
        while(q.empty()==false)
        {
            t=q.top();
            q.pop();
            if(t==des)
                ans=min(ans,judge[t].sum);
            else if(judge[t].sum<ans)
            {
                int loc=t.find('0');
                int x=loc/3;
                int y=loc%3;
                int step=judge[t].sum;
                if(x-1>=0)
                {
                    swap(t[loc],t[loc-3]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        cal_num(t);
                        q.push(t);
                    }
                    swap(t[loc],t[loc-3]);
                }
                if(y-1>=0)
                {
                    swap(t[loc],t[loc-1]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        cal_num(t);
                        q.push(t);
                    }
                    swap(t[loc],t[loc-1]);
                }
                if(y+1<=2)
                {
                    swap(t[loc],t[loc+1]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        cal_num(t);
                        q.push(t);
                    }
                    swap(t[loc],t[loc+1]);
                }
                if(x+1<=2)
                {
                    swap(t[loc],t[loc+3]);
                    if(judge[t].b==false)
                    {
                        judge[t].b=true;
                        judge[t].sum=step+1;
                        cal_num(t);
                        q.push(t);
                    }
                    swap(t[loc],t[loc+3]);
                }
            }
            if(judge[q.top()].num>=ans)
                break;
        }
    }
    
    int main()
    {
        string str;
        cin>>str;
        if(str==des)
            cout<<0<<endl;
        else
            BFS(str);
        if(ans==INIT)
            cout<<-1<<endl;
        else
            cout<<ans<<endl;
        return 0;
    }
    
    
  • 0
    @ 2018-05-02 21:17:04

    #include <iostream>
    using namespace std;
    #define INF 0x7fffffff
    char Koma[3][3]={{'1','2','3'},{'8','0','4'},{'7','6','5'}};
    int num=INF;
    struct team
    {
    char Base[3][3];
    };
    void Change(char & a,char & b)
    {
    char x;
    x=a;
    a=b;
    b=x;
    }
    bool Check(team h)
    {
    for(int a=0;a<3;a++)
    for(int b=0;b<3;b++)
    if(h.Base[a][b]!=Koma[a][b])
    return 0;
    return 1;
    }
    int bfs(team h,int count,int repead)
    {
    if(Check(h))
    {
    if(count<num)
    num=count;
    /*for(int a=0;a<3;a++)
    {
    for(int b=0;b<3;b++)
    cout<<h.Base[a][b]<<" ";
    cout<<endl;
    }
    */
    return 0;
    }
    if(count>=22)
    return 0;
    for(int a=0;a<3;a++)
    for(int b=0;b<3;b++)
    if(h.Base[a][b]=='0')
    {
    if(a-1>=0&&repead!=7)
    {
    Change(h.Base[a-1][b],h.Base[a][b]);
    bfs(h,count+1,2);
    Change(h.Base[a-1][b],h.Base[a][b]);
    }
    if(b-1>=0&&repead!=5)
    {
    Change(h.Base[a][b-1],h.Base[a][b]);
    bfs(h,count+1,4);
    Change(h.Base[a][b-1],h.Base[a][b]);
    }
    if(b+1<3&&repead!=4)
    {
    Change(h.Base[a][b+1],h.Base[a][b]);
    bfs(h,count+1,5);
    Change(h.Base[a][b+1],h.Base[a][b]);
    }
    if(a+1<3&&repead!=2)
    {
    Change(h.Base[a+1][b],h.Base[a][b]);
    bfs(h,count+1,7);
    Change(h.Base[a+1][b],h.Base[a][b]);
    }
    }
    }
    int main()
    {
    team h;
    for(int a=0;a<3;a++)
    for(int b=0;b<3;b++)
    cin>>h.Base[a][b];
    bfs(h,0,0);
    cout<<num;
    }

  • 0
    @ 2017-09-11 00:31:59

    之前《人工智能导论》课程的作业,采用面向对象方法设计的程序。

    #include <fstream>
    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    class StatusHeap;
    
    struct Status
    {
        int matrix[9] = {0};
        int key = 0, f = 0, g = 0, h = 0, pos0 = 0;
        Status* p = nullptr;
    
        Status() = default;
        explicit Status(Status*);
        ~Status() = default;
    
        void calcf();   // 计算 f 值
        int calckey();  // 计算康拓展开的 hash 值,进行查重
    
        void print(std::ostream &);
    
        Status* canGo(StatusHeap *, StatusHeap *, int);
    
        Status* canGoL(StatusHeap *, StatusHeap *); // “0”可以向左走,下面三个函数同理
        Status* canGoR(StatusHeap *, StatusHeap *);
        Status* canGoU(StatusHeap *, StatusHeap *);
        Status* canGoD(StatusHeap *, StatusHeap *);
    };
    
    class StatusHeap
    {
    private:
        Status *h[370000] = {nullptr};      // Status 指针数组
        bool hasit[370000] = {false};       // 用康拓展开 hash 判断是否在堆中
        int size;
    
    protected:
        int properParent(int);
    
    public:
        StatusHeap();
        ~StatusHeap();
    
        int Size();
    
        void insert(Status *s);
    
        Status *delMax();
    
        bool inHeap(int k);
    };
    
    // 康拓展开用 0!, 1!, ..., 8!
    static const int fac[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
    
    // 构造函数,拷贝matrix,记录父节点
    Status::Status(Status* pp)
    {
        p = pp;
        if(p) g = p->g + 1; else g = 0;
        if(p)
        {
            for(int i = 0; i < 9; ++i)
                matrix[i] = p->matrix[i];
            pos0 = p->pos0;
        }
    }
    
    void Status::calcf()
    {
        h = 0;
        if(matrix[0] != 1) h++;
        if(matrix[1] != 2) h++;
        if(matrix[2] != 3) h++;
        if(matrix[3] != 8) h++;
        if(matrix[5] != 4) h++;
        if(matrix[6] != 7) h++;
        if(matrix[7] != 6) h++;
        if(matrix[8] != 5) h++;
        f = g + h;
    }
    
    int Status::calckey()
    {
        int x = 0, count;
        for(int i = 0; i < 9; ++i)
        {
            count = 0;
            for(int j = i + 1; j < 9; ++j)
                if(matrix[i] < matrix[j]) ++count;
            x += count * fac[8 - i];
        }
        return x;
    }
    
    void Status::print(ostream &fout)
    {
        // 先打印父节点,再打印自己
        if(p && p->p) p->print(fout);
        fout << endl;
        fout << matrix[0] << ' ' << matrix[1] << ' ' << matrix[2] << endl;
        fout << matrix[3] << ' ' << matrix[4] << ' ' << matrix[5] << endl;
        fout << matrix[6] << ' ' << matrix[7] << ' ' << matrix[8] << endl;
    }
    
    Status* Status::canGoL(StatusHeap *open, StatusHeap *close)
    {
        // 如果“0”在第一列,则无法向左移。下面三个函数同理
        if(pos0 % 3 == 0) return nullptr;
        return canGo(open, close, -1);
    }
    
    Status* Status::canGoR(StatusHeap *open, StatusHeap *close)
    {
        if(pos0 % 3 == 2) return nullptr;
        return canGo(open, close, 1);
    }
    
    Status* Status::canGoU(StatusHeap *open, StatusHeap *close)
    {
        if(pos0 / 3 == 0) return nullptr;
        return canGo(open, close, -3);
    }
    
    Status* Status::canGoD(StatusHeap *open, StatusHeap *close)
    {
        if(pos0 / 3 == 2) return nullptr;
        return canGo(open, close, 3);
    }
    
    // 如果“0”可以移动,则调用此函数查重
    Status* Status::canGo(StatusHeap *open, StatusHeap *close, int delta)
    {
        // 移动数字块并重新计算key
        int x = matrix[pos0 + delta];
        matrix[pos0 + delta] = matrix[pos0];
        matrix[pos0] = x;
        int k = calckey();
    
        // 如果节点已出现过,则换回来,否则新建节点并返回指针
        if(open->inHeap(k) || close->inHeap(k))
        {
            x = matrix[pos0 + delta];
            matrix[pos0 + delta] = matrix[pos0];
            matrix[pos0] = x;
            return nullptr;
        } else {
            auto *newnode = new Status(this);
    
            x = matrix[pos0 + delta];
            matrix[pos0 + delta] = matrix[pos0];
            matrix[pos0] = x;
            newnode->key = newnode->calckey();
    
            newnode->pos0 = pos0 + delta;
            newnode->calcf();
    
            return newnode;
        }
    }
    
    
    int StatusHeap::properParent(int i)
    {
        int pf = h[i]->f, l = 1 + (i << 1), r = (i + 1) << 1;
        if(l >= size)
            return i;
        else
        {
            int lf = h[l]->f;
            if(r >= size)
            {
                if(pf > lf)
                    return l;
                else
                    return i;
            } else {
                int rf = h[r]->f;
                if((pf <= lf) && (pf <= rf))
                    return i;
                else
                {
                    if((lf < pf) && (lf <= rf))
                        return l;
                    else
                        return r;
                }
            }
        }
    }
    
    StatusHeap::StatusHeap() { size = 0; memset(hasit, 0, sizeof(bool) * 370000); }
    StatusHeap::~StatusHeap() { for(int i = 0; i < size; ++i) delete h[i]; }
    
    int StatusHeap::Size() { return size; }
    
    // 堆插入
    void StatusHeap::insert(Status *s)
    {
        int i = size++;
        h[i] = s;
        hasit[s->key] = true;
        while(i > 0)
        {
            int j = (i - 1) >> 1;
            if(h[j]->f <= h[i]->f) break;
            Status *t = h[j];
            h[j] = h[i];
            h[i] = t;
            i = j;
        }
    }
    
    // 删除堆顶元素
    Status *StatusHeap::delMax()
    {
        Status *max = h[0];
        int i = 0, j;
        h[0] = h[--size];
        hasit[max->key] = false;
        while(i != (j = properParent(i)))
        {
            Status *t = h[j];
            h[j] = h[i];
            h[i] = t;
            i = j;
        }
        return max;
    }
    
    // 查重
    bool StatusHeap::inHeap(int k)
    {
        return hasit[k];
    }
    
    int main(int argc, char** argv)
    {
    
            // 读入数据
            auto *cur = new Status(nullptr);
            char x;
            for(int i = 0; i < 9; ++i)
            {
                cin >> x;
                cur->matrix[i] = x - '0';
                if(x == '0') cur->pos0 = i;
            }
            cur->key = cur->calckey(); cur->calcf();
    
            // 新建堆,方便读取f最小值
            auto *open = new StatusHeap, *close = new StatusHeap;
            open->insert(cur);
    
            // 当OPEN表不为空
            while(open->Size() > 0)
            {
                // 取出最小值
                cur = open->delMax();
    
                // 如果OPEN堆顶是目标节点,则退出
                if(cur->h == 0)
                {
                    cout << cur->g << endl;
                    break;
                }
    
                // OPEN堆顶元素加入CLOSE
                close->insert(cur);
    
                // 向上下左右扩展节点,加入OPEN
                if(Status *a = cur->canGoL(open, close))
                {
                    open->insert(a);
                }
                if(Status *a = cur->canGoR(open, close))
                {
                    open->insert(a);
                }
                if(Status *a = cur->canGoU(open, close))
                {
                    open->insert(a);
                }
                if(Status *a = cur->canGoD(open, close))
                {
                    open->insert(a);
                }
            }
    
        return 0;
    }
    
    
  • 0
    @ 2017-09-09 16:16:22
    #include <bits/stdc++.h>
    using namespace std;
    #define IOS ios::sync_with_stdio(false)
    #define what_is(x) cerr << #x << " is " << x << endl
    #define rep(i, a, n) for (int i = a; i < n; i++)
    #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(), (x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int, int> PII;
    struct matrix{
        int arr[3][3];
        bool operator < (const matrix other) const{
            rep(i, 0, 3)
                rep(j, 0, 3) {
                    if (arr[i][j] < other.arr[i][j])
                        return true;
                    if (arr[i][j] > other.arr[i][j])
                        return false;
                }
            return false;
        }
    };
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    matrix a;
    matrix b = {
        .arr = {
            {1,2,3},
            {8,0,4},
            {7,6,5}
        }
    };
    int main() {
        //freopen("test.in", "r", stdin);
        char tmp;
        rep(i, 0, 3)
            rep(j, 0, 3) {
                scanf("%c", &tmp);
                a.arr[i][j] = tmp - '0';
            }
        queue<matrix> q;
        q.push(a);
        map<matrix, int> s;
        s[a] = 0;
        while (q.size() && s.find(b) == s.end()) {
            matrix head = q.front();
            q.pop();
            rep(x, 0, 3)
                rep(y, 0, 3) {
                    if (head.arr[x][y] != 0)
                        continue;
                    rep(i, 0, 4) {
                        int xx = x+dx[i];
                        int yy = y+dy[i];
                        if (0 <= xx && xx < 3 && 0 <= yy && yy < 3 ) {
                            matrix p = head;
                            swap(p.arr[x][y], p.arr[xx][yy]);
                            if (s.find(p) == s.end()) {
                                q.push(p);
                                s[p] = s[head] + 1;
                            }
                        }
                    }
                }
        }
        printf("%d\n", s[b]);
    
    
    }
    
    
  • 0
    @ 2017-07-25 00:17:54

    hash+双向bfs
    对每一个状态都计算它对应的位置数(这里使用状态(9进制)对应的10进制数),使用求余的hash来存储它的位置

    //2017/07/24 by:TBB000623/LJM000623
    //8_num_question
    //from Luogu1379/Vijos1360/CODEVS1225
    
    #include <cstdio>
    #include <iostream>
    #include <queue>
    #include <vector>
    #include <map>
    #include <cstdlib> 
    using namespace std;
    typedef unsigned u32;
    queue<u32>  qu;
    queue< pair<u32,int> >  requ;
    vector< vector< pair<u32,int> > >   hash_step,rehash_step;
    
    const u32 MOD=100019;
    u32 calc(const vector<int> &in) {
        u32 S=0;
        for(int i=0;i<9;i++)    S=9*S+in[i];
        return S;
    }
    vector<int> recalc(int in)  {
        vector<int> S;
        S.resize(9);
        for(int i=8;i>=0;i--)   S[i]=in%9,in/=9;
        return S;
    }
    vector< pair<u32,int> >::iterator   ser(u32 ha_in)  {
        vector< pair<u32,int> >::iterator   iter;
        for(iter=hash_step[ha_in%MOD].begin();iter!=hash_step[ha_in%MOD].end();iter++)  if(iter->first==ha_in)  break;
    //  if(iter==hash_step[ha_in%MOD].end())    cerr<<"A"<<ha_in<<endl;
        return iter;
    }
    vector< pair<u32,int> >::iterator   reser(u32 ha_in)    {
        vector< pair<u32,int> >::iterator   iter;
        for(iter=rehash_step[ha_in%MOD].begin();iter!=rehash_step[ha_in%MOD].end();iter++)  if(iter->first==ha_in)  break;
    //  if(iter==hash_step[ha_in%MOD].end())    cerr<<"A"<<ha_in<<endl;
        return iter;
    }
    int zero(const vector<int> &in) {
        int i=0;
        while(in[i]!=0) i++;
        return i;
    }
    
    inline u32  calc_left(vector<int> in,int zero_pos)  {
        swap(in[zero_pos],in[zero_pos-1]);
        return calc(in);
    }
    inline u32  calc_up(vector<int> in,int zero_pos)    {
        swap(in[zero_pos],in[zero_pos-3]);
        return calc(in);
    }
    inline u32  calc_right(vector<int> in,int zero_pos) {
        swap(in[zero_pos],in[zero_pos+1]);
        return calc(in);
    }
    inline u32  calc_down(vector<int> in,int zero_pos)  {
        swap(in[zero_pos],in[zero_pos+3]);
        return calc(in);
    }
    
    void bfs(int lim)   {
        while(!qu.empty())  {
            u32 a=qu.front();           
            vector<int> ve=recalc(a);
            int zero_pos=zero(ve);
            vector< pair<u32,int> >::iterator   iter=ser(a);        
            int ste=iter->second;
            if(ste>lim) break;
            qu.pop();
            
            if(ste>=16) continue;
            
            if(zero_pos%3!=0)   {
                u32 k=calc_left(ve,zero_pos);
                iter=ser(k);
                if(iter==hash_step[k%MOD].end())    {
                    hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                    qu.push(k);
                }
            }
            if(zero_pos%3!=2)   {
                u32 k=calc_right(ve,zero_pos);
                iter=ser(k);
                if(iter==hash_step[k%MOD].end())    {
                    hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                    qu.push(k);
                }
            }
            if(zero_pos>=3) {
                u32 k=calc_up(ve,zero_pos);
                iter=ser(k);
                if(iter==hash_step[k%MOD].end())    {
                    hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                    qu.push(k);
                }
            }
            if(zero_pos<6)  {
                u32 k=calc_down(ve,zero_pos);
                iter=ser(k);
                if(iter==hash_step[k%MOD].end())    {
                    hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                    qu.push(k);
                }
            }
        }
    }
    void rebfs(int lim) {
        while(!requ.empty())    {
            pair<u32,int>   pa=requ.front();    
    //      cout<<pa.first<<" "<<pa.second<<endl;
            vector< pair<u32,int> >::iterator   iter=ser(pa.first);
            if(iter!=hash_step[pa.first%MOD].end()) {
                cout<<iter->second+pa.second<<endl;
                exit(0);
            }
    //      hash_step[pa.first%MOD].push_back(pa);
            vector<int> ve=recalc(pa.first);
            int zero_pos=zero(ve);
            
            if(pa.second>lim)   break;
            requ.pop();
            
            
            if(zero_pos%3!=0)   {
                u32 k=calc_left(ve,zero_pos);
                iter=reser(k);
                if(iter==rehash_step[k%MOD].end())  {
                    rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                    requ.push(pair<u32,int>(k,pa.second+1));
                }
            }
            if(zero_pos%3!=2)   {
                u32 k=calc_right(ve,zero_pos);
                iter=reser(k);
                if(iter==rehash_step[k%MOD].end())  {
                    rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                    requ.push(pair<u32,int>(k,pa.second+1));
                }
            }
            if(zero_pos>=3) {
                u32 k=calc_up(ve,zero_pos);
                iter=reser(k);
                if(iter==rehash_step[k%MOD].end())  {
                    rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                    requ.push(pair<u32,int>(k,pa.second+1));
                }
            }
            if(zero_pos<6)  {
                u32 k=calc_down(ve,zero_pos);
                iter=reser(k);
                if(iter==rehash_step[k%MOD].end())  {
                    rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                    requ.push(pair<u32,int>(k,pa.second+1));
                }
            }
        }
    }
    int main()  {
        int be_pos[9]={1,2,3,8,0,4,7,6,5};
        int en_pos[9];
        char in[10];
        scanf("%s",in);
        hash_step.resize(MOD);
        rehash_step.resize(MOD);
        for(int i=0;i<9;i++)    en_pos[i]=in[i]-'0';
        vector<int> be_ve(&be_pos[0],&be_pos[9]);
        vector<int> en_ve(&en_pos[0],&en_pos[9]);
        int hash_be_ve=calc(be_ve);
        int hash_en_ve=calc(en_ve);
        hash_step[hash_be_ve%MOD].push_back(pair<u32,int>(hash_be_ve,0));
        qu.push(hash_be_ve);
        requ.push(pair<u32,int>(hash_en_ve,0));
        rehash_step[hash_en_ve%MOD].push_back(pair<u32,int>(hash_en_ve,0));
        
        int limts;
        for(limts=0;limts<100;limts++)  {
            bfs(limts);
            rebfs(limts);
        }
        cout<<"No solution!"<<endl;
        return 0;
    }
    
  • 0
    @ 2017-07-08 17:04:13
    #include<cstring>
    #include <stdio.h>
    
    #include<iostream>
    #include<cstdlib>
    #include<algorithm>
    #include<stack>
    
    #include<queue>
    #include<list>
    #include<cmath>
    #include<string>
    #include<map>
    //#include<stdafx.h>
    using namespace std;
    struct node {
        int  x[3][3],step;
    
    } in;
    int en[3][3]= { { 1,2,3 },{ 8,0,4 },{ 7,6,5 } };
    queue<node>p;
    map <int, bool> ts;
    bool l(node u) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (u.x[i][j] != en[i][j])
                    return false;
        return true;
    }
    int magicpro(node d) {
        int fin=0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                fin *= 10;
                fin += d.x[i][j];
            }
        return fin;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        int y;
        cin >> y;
        for (int i = 2; i >=0; i--)
            for (int j =2; j >=0; j--){
                
                
                in.x[i][j] = y % 10;
                y /= 10;
            }
        in.step = 0;
        
        
        
        p.push(in);
        
        while (true) {
            int o, s;
            if (l(p.front()) == true)
            {
                cout << p.front().step;
                break;
            }
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                    if (p.front().x[i][j] == 0)
                    {
                        o = i;
                        s = j;
                    }
            node ans = p.front();
            p.pop();
            ans.step++;
            if (ts[magicpro(ans)] == true)
                continue;
            else
                ts[magicpro(ans)] = true;
            if (s > 0)
            {
                swap(ans.x[o][s], ans.x[o][s - 1]);
                p.push(ans);
                swap(ans.x[o][s], ans.x[o][s - 1]);
            }
            if (s <2)
            {
                swap(ans.x[o][s], ans.x[o][s + 1]);
                p.push(ans);
                swap(ans.x[o][s], ans.x[o][s +1]);
            }
            if (o > 0)
            {
                swap(ans.x[o][s], ans.x[o-1][s]);
                p.push(ans);
                swap(ans.x[o][s], ans.x[o-1][s ]);
            }
            if (o<2)
            {
                swap(ans.x[o][s], ans.x[o+1][s ]);
                p.push(ans);
                swap(ans.x[o][s], ans.x[o+1][s ]);
            }
        }
        //system("pause");
        return 0;
    }
    

    这题实际上很水,就是BFS+哈希。但是一开始不太会写哈希,导致爆内存,直到知道了map这个好东西,直接秒掉了。(ps:为了方便乱写的变量民请无视……)

  • 0
    @ 2017-07-08 14:07:10

    暴力bfs+判重

    #include<iostream>
    using namespace std;
    int head,tail;
    short f[10000000][9];
    int step[10000000]={0},zero[10000000];
    int ans=-1;
    bool judge[87654321]={0};
    
    bool done(short a[])
    {
        int bit_8=0;
        for(int i=0;i<=7;i++)
        {
            bit_8*=10;
            bit_8+=a[i];
        }
        if(judge[bit_8]==0)
        {
            judge[bit_8]=1;
            return 0;
        }
        else
            return 1;
    }
    
    void start()
    {
        int input;
        cin>>input;
        for(int i=0;i<9;i++)
        {
            f[1][8-i]=input % 10;
            input=input/10;
            if(f[1][8-i]==0)
                zero[1]=8-i;
        }
        if(f[1][0]==1&&f[1][1]==2&&f[1][2]==3
        &&f[1][3]==8&&f[1][4]==0&&f[1][5]==4
        &&f[1][6]==7&&f[1][7]==6&&f[1][8]==5)
        {ans=0;
        cout<<ans;
        }
    }
    
    void if_finished(short a[])
    {
        int bit_8=0;
        for(int i=0;i<=8;i++)
        {
            bit_8*=10;
            bit_8+=a[i];
        }
        if(bit_8==123804765)
        {
            ans=step[head]+1;
            cout<<ans;
        }
    }
    
    void move(int type)
    {
        if(ans!=-1)return;
        short mov[4]={-3,3,-1,1};
        short a[9];
        for(int i=0;i<9;i++)
            a[i]=f[head][i];
        a[zero[head]]=a[zero[head]+mov[type]];
        a[zero[head]+mov[type]]=0;
        if_finished(a);
        if(done(a)==0)
        {
            tail++;
            for(int i=0;i<9;i++)
            f[tail][i]=a[i];
            zero[tail]=zero[head]+mov[type];
            step[tail]=step[head]+1;
        }
    }
    
    int main()
    {
        start();
        head=1;tail=1;
        while(ans==-1&&head<=tail)
        {
            if(zero[head]!=0&&zero[head]!=1&&zero[head]!=2)
                move(0);
            if(zero[head]!=6&&zero[head]!=7&&zero[head]!=8)
                move(1);
            if(zero[head]!=0&&zero[head]!=3&&zero[head]!=6)
                move(2);
            if(zero[head]!=2&&zero[head]!=5&&zero[head]!=8)
                move(3);
            head++;
        }
        if(ans==-1)
            cout<<-1;
        return 0;
    }
    
  • 0
    @ 2017-04-07 16:41:42

    BFS

    #include <queue>
    #include <algorithm>
    #include <cstdio>
    #include <map>
    #include <iostream>
    using namespace std;
    int target_[3][3]={{1,2,3},{8,0,4},{7,6,5}};
    
    struct Stat 
    {
        int c[3][3];
        Stat(int _c[3][3])
        {
            for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
            {
                c[i][j] = _c[i][j];
            }
        }
        Stat(const Stat &other)
        {
            for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
            {
                c[i][j] = other.c[i][j];
            }
        }
        bool operator< (const Stat &other) const
        {
            for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
              {
                if (c[i][j] < other.c[i][j]) return true;
                if (c[i][j] > other.c[i][j]) return false;
              }
            return false;
        }
    };
    
    const Stat target(target_);
    
    map <Stat,int> Map;
    queue <Stat> que;
    int main()
    {
        
        Map.clear();
        int orig_[3][3];
        for(int i = 0; i < 3; i++)
        for (int j = 0; j< 3;j++)
            scanf("%1d",&orig_[i][j]);
        Stat orig(orig_);
        que.push(orig);
        Map[orig] = 0;
        while (que.size() && Map.find(target) == Map.end())
        {
            Stat s = que.front(); que.pop();
            int count = Map[s],blank_x=-1,blank_y=-1;
            for (int i = 0; i < 3 && blank_x == -1; i++)
            {
                for (int j = 0; j < 3; j++)
                    if (s.c[i][j] == 0)
                    {
                        blank_x = i;
                        blank_y = j;
                        break;
                    }
            }
            int dx[4]={-1,1,0,0}, dy[4] = {0,0,1,-1};
            for (int i = 0; i < 4; i++)
            {
                int nx = blank_x + dx[i], ny = blank_y +dy[i];
                if (nx >=0 && nx < 3 && ny>=0 && ny<3)
                {
                    Stat ns(s);
                    ns.c[blank_x][blank_y] = ns.c[nx][ny];
                    ns.c[nx][ny] = 0;
                    if (Map.find(ns) == Map.end())
                    {
                        que.push(ns);
                        Map[ns] = Map[s] + 1;
                    }   
                }
            }   
        } 
        cout << Map[target] << endl;    
        
    }
    
  • 0
    @ 2017-01-19 13:59:32

    人生第一个启发式搜索……0ms,很强势
    具体见注释:

    #include <iostream>
    #include <deque>
    #include <algorithm>
    #include <cstdlib>
    #define _abs(x) (x>=0?x:-x)//绝对值函数
    #define h_size 14233333//哈希表大小
    #define hash(x) (x%h_size)
    using namespace std;
    typedef pair<int,int> pii;
    const int _end=123804765,_enp[2][9]={{1,0,0,0,1,2,2,2,1},{1,0,1,2,2,2,1,0,0}};//end为目标状态,enp[0][i]表示目标状态中数字i所在的行,enp[1][i]表示数字i所在的列
    int _sta;//开始状态
    bool _clo[h_size];//a*算法的close表
    deque<pii> _ol;//a*算法的open表
    int h(int key)//估值函数,使用曼哈顿距离估值
    {
        int _map[3][3],_kp[2][9],sum=0;
        for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_kp[0][key%10]=i,_kp[1][key%10]=j,key/=10;
        for(int i=0;i<9;i++)sum+=abs(_kp[0][i]-_enp[0][i])+abs(_kp[1][i]-_enp[1][i]);
        return sum;
    }
    int move(int key,char _ctr)//移动数字0函数,u表示向上,d表示向下,l表示向左,r表示向右
    {
        int _kb=key,_map[3][3],i0,j0;
        for(int i=2;i>=0;i--)for(int j=2;j>=0;j--){_map[i][j]=_kb%10,_kb/=10;if(_map[i][j]==0)i0=i,j0=j;}
        switch(_ctr)//如果无法扩展(即到达边界)就返回移动前的值
        {
            case 'u':if(i0==0)return key;swap(_map[i0][j0],_map[i0-1][j0]);break;
            case 'd':if(i0==2)return key;swap(_map[i0][j0],_map[i0+1][j0]);break;
            case 'l':if(j0==0)return key;swap(_map[i0][j0],_map[i0][j0-1]);break;
            case 'r':if(j0==2)return key;swap(_map[i0][j0],_map[i0][j0+1]);break;
        }
        for(int i=0;i<3;i++)for(int j=0;j<3;j++)_kb=_kb*10+_map[i][j];
        return _kb;
    }
    bool cmp(pii a,pii b){return a.second<b.second;}//二分查找比较函数
    void work(pii _nex)//处理新状态
    {
        if(_nex.first==_end)cout<<_nex.second-h(_nex.first),exit(0);//发现正解,直接输出并结束程序
        if(!_clo[hash(_nex.first)])_ol.insert(lower_bound(_ol.begin(),_ol.end(),_nex,cmp),_nex);//二分查找插入新状态
    }
    int main()
    {
        cin>>_sta;
        _ol.push_back(make_pair(_sta,h(_sta)));//把开始状态加入到open表中
        while(!_ol.empty())//处理open表
        {
            pii _now=_ol.front();
            _ol.pop_front(),_clo[hash(_now.first)]=1;//把当前open表中的最优状态取出并加入到close表中
            int _nex=move(_now.first,'u');//扩展新状态
            work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'d');
            work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'l');
            work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'r');
            work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1));
        }
        return 0;
    }
    
  • 0
    @ 2016-11-20 21:16:39

    纯广搜,暴力AC
    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <string>
    #include <map>
    using namespace std;
    struct que{
    char m[3][3];
    int step;
    } q[1000000];
    map <string,bool> vis;           //用map模仿hash 
    int h=0,t=0;
    char aim[3][3]={{'1','2','3'},{'8','0','4'},{'7','6','5'}};
    int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1};
    char m[3][3];
    string s;
    bool judge(char a[][3],char b[][3]){    //判断是否与目标相同 
    for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
       if(a[i][j]!=b[i][j])
         return false;
    return true;
    }
    void insert(char a[][3],int step,string s){   //入队 
    t++;
    for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
       q[t].m[i][j]=a[i][j];
    q[t].step=step;
    vis[s]=true;                 //访问标记 
    }
    void take(char a[][3]){          //出队 
    h++;
    for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
       a[i][j]=q[h].m[i][j];
    }
    void work(char a[][3],int step){
    int x,y;
    for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
       if(a[i][j]=='0'){
     x=i,y=j;
     break;
    }
    for(int i=0;i<4;i++)
     if(x+xx[i]>=0 && y+yy[i]>=0 && x+xx[i]<3 && y+yy[i]<3){
      a[x][y]=a[x+xx[i]][y+yy[i]];
    a[x+xx[i]][y+yy[i]]='0';
    string s;                   //把矩阵转换成一个string来作为访问 
       for(int j=0;j<3;j++)
         for(int k=0;k<3;k++)
           s+=a[j][k];
    if(vis[s]!=true)
     insert(a,step+1,s);
    a[x+xx[i]][y+yy[i]]=a[x][y];
    a[x][y]='0';
     }
    }
    int bfs(){
    char k[3][3];
    while(h<t){
     take(k);
     if(judge(k,aim))
      return q[h].step;
     work(k,q[h].step);
    }
    }
    int main(){
    int cnt=0;
    cin>>s;
    for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
       m[i][j]=s[cnt++];
    insert(m,0,s);
    vis[s]=true;
    printf("%d\n",bfs());
    return 0;
    }

  • 0
    @ 2016-11-13 21:21:43

    数据好弱啊...根本不用A*
    暴力+康托展开就好了...
    测试数据 #0: Accepted, time = 0 ms, mem = 9028 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 9028 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 9028 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 9028 KiB, score = 10
    测试数据 #4: Accepted, time = 31 ms, mem = 9028 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 9032 KiB, score = 10
    测试数据 #6: Accepted, time = 31 ms, mem = 9028 KiB, score = 20
    测试数据 #7: Accepted, time = 31 ms, mem = 9028 KiB, score = 20
    Accepted, time = 154 ms, mem = 9032 KiB, score = 100
    pascal
    program P1360;
    const
    p:array[0..9] of longint=(1,1,2,6,24,120,720,5040,40320,362880);
    final:array[1..9] of shortint=(1,2,3,8,0,4,7,6,5);
    type
    arr=array[1..9] of shortint;
    ty=record
    map:arr;
    depth,loc:longint;
    end;
    var
    list:array[1..400000] of ty;
    hash:array[0..400000] of boolean;
    i,j,t,open,closed:longint;
    start:arr;
    function find(x:arr):boolean;
    var
    i:longint;
    begin
    for i:=1 to 9 do if x[i]<>final[i] then exit(false);
    exit(true);
    end;
    function con(x:arr):longint; //康托展开
    var
    i,t:longint;
    begin
    con:=0;
    for i:=1 to 9 do
    begin
    t:=x[i];
    for j:=1 to i do if x[j]<x[i] then dec(t);
    inc(con,t*p[9-i]);
    end;
    end;
    procedure dfs(x:shortint);
    var
    t:arr;
    temp:longint;
    begin
    t:=list[open].map;
    t[list[open].loc]:=t[x];
    t[x]:=0;
    temp:=con(t);
    if find(t) then
    begin
    writeln(list[open].depth+1);
    halt;
    end;
    if not hash[temp] then
    begin
    list[closed].map:=t;
    list[closed].depth:=list[open].depth+1;
    list[closed].loc:=x;
    hash[temp]:=true;
    inc(closed);
    end;
    end;
    begin
    readln(t);
    for i:=9 downto 1 do
    begin
    start[i]:=t mod 10;
    if start[i]=0 then list[1].loc:=i;
    t:=t div 10;
    end;
    list[1].map:=start;
    list[1].depth:=0;
    open:=1;closed:=2;
    if find(start) then
    begin
    writeln(0);
    halt;
    end;
    fillchar(hash,sizeof(hash),false);
    hash[con(start)]:=true;
    repeat
    t:=list[open].loc;
    if (t<>3) and (t<>6) and (t<>9) then dfs(t+1);
    if (t<>1) and (t<>4) and (t<>7) then dfs(t-1);
    if (t>3) then dfs(t-3);
    if (t<7) then dfs(t+3);
    inc(open);
    until open=closed;
    end.

  • 0
    @ 2016-07-30 20:44:17

    '''c++
    #include<iostream>
    #include<cstdio>
    #include<queue>
    #include<string>
    #define M 1000003
    using namespace std;
    const int goal[10]={0,1,2,3,8,0,4,7,6,5};
    int ans;
    struct Node{
    int s[10],step;
    };
    Node hash[M];
    int head[M],next[M];
    int hash_size;

    queue<Node> q;
    int findzero(Node a){
    int pos=1;
    while(1)
    {
    if(a.s[pos]==0)
    break;
    pos++;
    }

    return pos;
    }
    bool check(Node x){
    for(int i=1;i<=9;i++)
    {
    if(x.s[i]!=goal[i])
    return false;
    }
    return true;
    }
    //hashÅÐÖØ
    bool same(Node x,Node y){
    for(int i=1;i<=9;i++)
    {
    if(x.s[i]!=y.s[i])
    return false;
    }
    return true;
    }
    int create_hash(Node x){
    int hashnum=0;
    for(int i=1;i<=9;i++)
    hashnum=hashnum*10+x.s[i];
    return hashnum % M;

    }
    bool insert(Node x){
    int h=create_hash(x);
    int i=head[h];
    while(i)
    {
    if(same(x,hash[i]))
    return false;
    i=next[i];
    }
    hash_size++;
    next[hash_size]=head[h];
    head[h]=hash_size;
    hash[hash_size]=x;
    return true;
    }
    int main(){
    string start;
    cin>>start;//¶ÁÈë
    Node st;
    st.step=0;
    for(int i=0;i<9;i++)
    st.s[i+1]=start[i]-'0';//×Ö·ûתÊý×Ö
    insert(st);
    q.push(st);//bfs
    while(!q.empty()){
    Node head=q.front();
    q.pop();//³ö¶ÓÁÐ
    if(check(head))
    {
    ans=head.step;
    break;
    }
    //¼ì²é
    Node move;
    int pos=findzero(head);
    if(pos>=3)
    {
    move=head;
    int swappos=pos-3;
    swap(move.s[pos],move.s[swappos]);
    move.step++;
    if(insert(move))
    q.push(move);
    }
    //0ÏòÉÏ 1 2 3²»ÐÐ
    if(pos<=6){
    move=head;
    int swappos=pos+3;
    swap(move.s[pos],move.s[swappos]);
    move.step++;
    if(insert(move))
    q.push(move);
    }
    //0ÏòÏ 7 8 9²»ÐÐ
    if(pos % 3!=0){
    move=head;
    int swappos=pos+1;
    swap(move.s[pos],move.s[swappos]);
    move.step++;
    if(insert(move))
    q.push(move);
    }
    //0Ïò×ó 3 6 9ÎÞ·¨Ïò×ó
    if(pos % 3!=1){
    move=head;
    int swappos=pos-1;
    swap(move.s[pos],move.s[swappos]);
    move.step++;

    if(insert(move))
    q.push(move);
    }
    //0ÏòÓÒ 1 4 7ÎÞ·¨ÏòÓÒ

    }
    printf("%d",ans);

    return 0;
    }
    '''

  • 0
    @ 2016-07-23 17:56:13

    link
    AC50

信息

ID
1360
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
3778
已通过
911
通过率
24%
被复制
7
上传者