美文网首页Android菜鸟数据结构和算法分析
宽度优先遍历求解8数码问题

宽度优先遍历求解8数码问题

作者: 上行彩虹人 | 来源:发表于2017-08-02 17:17 被阅读27次

    数据结构描述

    typedef struct node {
        int a[3][3];
        struct node *pre;
        int x,y;
    } *Pnode,Node;
    

    a数组存放该节点的状态
    pre指针指向该节点的父节点

    queue<Pnode> open;
    

    open表是一个先进先出的队列

    问题是否有解的判断

        //判断是否有解
        int a[9],b[9];
        for(int i=0; i<9; i++) {
            a[i]=Phead->a[i/3][i%3] ;
            b[i]=target[i/3][i%3];
        }
        int t1=0,t2=0;
        for(int i=8; i>=0; i--)
            for(int j=i-1; j>=0; j--) {
                if(a[i]!=0)
                    if(a[i]<a[j])
                        t1++;
                if(b[i]!=0)
                    if(b[i]<b[j])
                        t2++;
            }
    
        printf("逆序数N1=%d 逆序数N2=%d\n",t1,t2);
        if(t1%2!=t2%2) {
            printf("该问题无解");
            return 0;
        }
    

    其实状态和目标状态必须同为奇序列或同为偶序列(0不加入计算)

    源代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<queue>
    #include<cstring>
    
    using namespace std;
    typedef struct node {
        int a[3][3];
        struct node *pre;
        int x,y;
    } *Pnode,Node;
    
    
    int Check(Pnode tem);
    void bfs();
    void up(Pnode tem);
    void Right(Pnode ptm);
    void Left(Pnode ptm);
    void Down(Pnode ptm);
    void Up(Pnode ptm);
    void show(Pnode tem);
    
    Pnode Phead;
    queue<Pnode> open;
    
    
    int flag=0;
    
    int target[3][3]= {3,6,8,2,5,7,0,1,4};
    
    int main() {
    
        Phead =(Pnode)malloc(sizeof(Node));
        Phead->pre =NULL;
        printf("请输入当前状态:\n");
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) {
                scanf("%d",&Phead->a[i][j]);
                if(Phead->a[i][j]==0) {
                    Phead->x=i;
                    Phead->y=j;
                }
            }
        printf("请输入目标:\n");
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) scanf("%d",&target[i][j]);
    
        //判断是否有解
        int a[9],b[9];
        for(int i=0; i<9; i++) {
            a[i]=Phead->a[i/3][i%3] ;
            b[i]=target[i/3][i%3];
        }
        int t1=0,t2=0;
        for(int i=8; i>=0; i--)
            for(int j=i-1; j>=0; j--) {
                if(a[i]!=0)
                    if(a[i]<a[j])
                        t1++;
                if(b[i]!=0)
                    if(b[i]<b[j])
                        t2++;
            }
    
        printf("逆序数N1=%d 逆序数N2=%d\n",t1,t2);
        if(t1%2!=t2%2) {
            printf("该问题无解");
            return 0;
        }
        bfs();
        return 0;
    }
    
    void bfs() {
        open.push(Phead);
        Check(Phead);
        while(!open.empty()&&flag==0) {
            Pnode tem=open.front();
    
            if(flag==0)
                Up(tem);
            if(flag==0)
                Down(tem);
            if(flag==0)
                Left(tem);
            if(flag==0)
                Right(tem);
    
            open.pop();
        }
    
    }
    
    void Up(Pnode ptm) {
        Pnode tem= (Pnode)malloc(sizeof(Node));
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
        tem->x=ptm->x;
        tem->y=ptm->y;
        int x=ptm->x,y=ptm->y;
        if(x==0) return ;
        int t=tem->a[x][y];
        tem->a[x][y]=tem->a[x-1][y] ;
        tem->a[x-1][y]=t;
        tem->x=x-1;
        int n=1;
        int index=0;
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) {
                index+=tem->a[i][j]*n;
                n=n*10;
            }
    
        tem->pre=ptm;
        if(Check(tem)==0) {
            open.push(tem);
        }
    
    
    }
    
    void Down(Pnode ptm) {
        Pnode tem= (Pnode)malloc(sizeof(Node));
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
        tem->x=ptm->x;
        tem->y=ptm->y;
        int x=ptm->x,y=ptm->y;
        if(x==2) return ;
        int t=tem->a[x][y];
        tem->a[x][y]=tem->a[x+1][y] ;
        tem->a[x+1][y]=t;
        tem->x=x+1;
        int n=1;
        int index=0;
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) {
                index+=tem->a[i][j]*n;
                n=n*10;
            }
    
        tem->pre=ptm;
        if(Check(tem)==0) {
            open.push(tem);
        }
    
    
    }
    
    void Left(Pnode ptm) {
        Pnode tem= (Pnode)malloc(sizeof(Node));
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
        tem->x=ptm->x;
        tem->y=ptm->y;
        int x=ptm->x,y=ptm->y;
        if(y==0) return ;
        int t=tem->a[x][y];
        tem->a[x][y]=tem->a[x][y-1] ;
        tem->a[x][y-1]=t;
        tem->y=y-1;
        int n=1;
        int index=0;
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) {
                index+=tem->a[i][j]*n;
                n=n*10;
            }
    
        tem->pre=ptm;
        if(Check(tem)==0) {
            open.push(tem);
        }
    
    
    }
    
    void Right(Pnode ptm) {
        Pnode tem= (Pnode)malloc(sizeof(Node));
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
        tem->x=ptm->x;
        tem->y=ptm->y;
        int x=ptm->x,y=ptm->y;
        if(y==2) return ;
        int t=tem->a[x][y];
        tem->a[x][y]=tem->a[x][y+1] ;
        tem->a[x][y+1]=t;
        tem->y=y+1;
        int n=1;
        int index=0;
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) {
                index+=tem->a[i][j]*n;
                n=n*10;
            }
        tem->pre=ptm;
        if(Check(tem)==0) {
            open.push(tem);
        }
    
    }
    
    
    
    int Check(Pnode tem) {
    
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
                if(tem->a[i][j]!=target[i][j]) {
                    //  printf("falg=%d\n",flag);
                    return 0;
                }
        flag=1;
        while(tem!=NULL&&flag==1) {
            show(tem);
            tem=tem->pre;
            //free(tem);
        }
        printf("找到解|");
        return 1;
    }
    
    
    void show(Pnode tem) {
        printf("---------\n");
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++)
                printf("%d ",tem->a[i][j]);
            printf("\n");
        }
        printf("---------\n");
    }
    
    

    相关文章

      网友评论

        本文标题:宽度优先遍历求解8数码问题

        本文链接:https://www.haomeiwen.com/subject/kprylxtx.html