• 注册
  • 关于作者
    企业认证:趣记站长
    关注 6 粉丝 4 喜欢 9 内容 992
    江西省·南昌市
    聊天 送礼
    • 查看作者
    • 拼图游戏的算法

      相信大家都玩过"滑块拼图"游戏!

        大概说一下 :假如一副图是由几个部分拼凑成的,现在要你把这些散块拼凑成一副完整的图片

                    也可以是几个数字来拼凑

        比如 3*3的格子

              1 2 3

              4 5 6

              7 8     (相当于原始矩阵)

      有一个格子是空的现在要你组合成

           1 2 7

           3 6 4

           5 8          (目标矩阵)

      问题是编写一种算法 能根据输入的原始图形(矩阵)拼凑成目标图形(目标矩阵) 要求是步数最少(耗时间最少)

        #include"iostream.h"

      struct node{

      int nodesun[4][4];

      int x,y;

      }path[1000];

      int zx[4]={-1,0,1,0};

      int zy[4]={0,-1,0,1};

      int top;

      int desti[4][4];//目标状态

      int detect(struct node *p)

      {int i,j;

        for(i=1;i<4;i++)

           for(j=1;j<4;j++)

         if(p->nodesun[i][j]!=desti[i][j])

          return 0;

        return 1;

      }

      void printlj()

      {int tempt;

      int i,j;

      tempt=1;

      while(tempt<=top)

      {    for(i=1;i<4;i++)

           for(j=1;j<4;j++)

        {cout<<path[tempt].nodesun[i][j];

         if(j==3)

          cout<<" "<<endl;

        }

        tempt++;

      }

      }

         

         

      void main()

      { //初始化

        int i,j,m,n,f;

        int temp,find=0;

        top=1;

      for(i=1;i<4;i++)

           for(j=1;j<4;j++)

        {cout<<"请输入第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;

         cin>>temp;

         path[1].nodesun[i][j]=temp;

        }

        cout<<"请输入初始状态的空格的位置(行)"<<endl;

        cin>>temp;

        path[1].x=temp;

      cout<<"请输入初始状态的空格的位置(列)"<<endl;

        cin>>temp;

        path[1].y=temp;

      //目标状态

      for(i=1;i<4;i++)

           for(j=1;j<4;j++)

        {cout<<"请输入目标状态第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;

         cin>>temp;

         desti[i][j]=temp;

        }

        //深度优先搜索

      while(!find)

      { m=path[top].x;

        n=path[top].y ;

        for(f=0;f<4;f++)

        {i=m+zx[f];

         j=n+zy[f];

         if(i>=1&&i<=3&&j>=1&&j<=3)

         {top++;

          path[top]=path[top-1];

      path[top].nodesun[m][n]=path[top-1].nodesun[i][j];

      path[top].nodesun[i][j]=0;

      path[top].x=i;

      path[top].y=j;

         if(detect(&path[top]))

         {printlj();

         find=1;

         break;

         }

         break;

         }//if

        

        }//for

         

         }//while

      }

      #include"iostream.h"

      struct node{

      int nodesun[4][4];

      int pre;

      int x,y;

      }path[400];

      int zx[4]={-1,0,1,0};

      int zy[4]={0,-1,0,1};

      int front,rear;

      int desti[4][4];//目标状态

      int detect(struct node *p)

      {int i,j;

        for(i=1;i<4;i++)

           for(j=1;j<4;j++)

         if(p->nodesun[i][j]!=desti[i][j])

          return 0;

        return 1;

      }

      void printlj()

      {int tempt;

      int i,j;

      tempt=rear;

      while(tempt!=0)

      {    for(i=1;i<4;i++)

           for(j=1;j<4;j++)

        {cout<<path[tempt].nodesun[i][j];

         if(j==3)

          cout<<" "<<endl;

        }

        tempt=path[tempt].pre;

      }

      }

         

         

      void main()

      { //初始化

        int i,j,m,n,f;

        int temp,find=0;

        front=rear=1;

        path[1].pre=0;

      for(i=1;i<4;i++)

           for(j=1;j<4;j++)

        {cout<<"请输入第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;

         cin>>temp;

         path[1].nodesun[i][j]=temp;

        }

        cout<<"请输入初始状态的空格的位置(行)"<<endl;

        cin>>temp;

        path[1].x=temp;

      cout<<"请输入初始状态的空格的位置(列)"<<endl;

        cin>>temp;

        path[1].y=temp;

      //目标状态

      for(i=1;i<4;i++)

           for(j=1;j<4;j++)

        {cout<<"请输入目标状态第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;

         cin>>temp;

         desti[i][j]=temp;

        }

        //广度优先搜索

      while(front<=rear&&!find)

      { m=path[front].x;

        n=path[front].y ;

        for(f=0;f<4;f++)

        {i=m+zx[f];

         j=n+zy[f];

         if(i>=1&&i<=3&&j>=1&&j<=3)

         {rear++;

          path[rear]=path[front];

      path[rear].nodesun[m][n]=path[front].nodesun[i][j];

      path[rear].nodesun[i][j]=0;

      path[rear].pre=front;

      path[rear].x=i;

      path[rear].y=j;

         if(detect(&path[rear]))

         {printlj();

         find=1;

         break;

         }

         }

        }

         front++;

         }

      }

      上面是用最简单的深度优先,广度优先直接搜索得来得,

      八皇后问题的高效解法-递归版
      贪心算法在背包中的应用,五子棋的核心算法,关联规则挖掘算法综述,九连环游戏算法递归实现,八皇后问题的高效解法-递归版,拼图游戏的算法,人民币大小写转换算法,CRC循环校验的具体算法,上楼梯算法的java实现,解决排列组合问题的通用算法,杨辉三角形,水仙花数,刘徽《九章算术》中的勾股数,八皇后问题的java实现,图像分割中阈值的自动选取的研究及其算法实现,高精度乘法和阶乘,RSA算法介绍,黑洞数的验证,算法一词的由来,什么是算法
      算法

      毫无AI可言,这并不说明我不能写出其更好得算法,这里最简单得的估价函数f(x)=g(x)+h(x)

      g(x)用初始化的节点到当前的节点的路径长度来表示h(x)启发函数用当前状态和目标状态的位置不同的个数来表

      到156.com可以看我的根多文章 

      八皇后问题的高效解法-递归版
      贪心算法在背包中的应用,五子棋的核心算法,关联规则挖掘算法综述,九连环游戏算法递归实现,八皇后问题的高效解法-递归版,拼图游戏的算法,人民币大小写转换算法,CRC循环校验的具体算法,上楼梯算法的java实现,解决排列组合问题的通用算法,杨辉三角形,水仙花数,刘徽《九章算术》中的勾股数,八皇后问题的java实现,图像分割中阈值的自动选取的研究及其算法实现,高精度乘法和阶乘,RSA算法介绍,黑洞数的验证,算法一词的由来,什么是算法
      算法

    • 0
    • 0
    • 0
    • 93
    • 单栏布局 侧栏位置: