c++ 八数码问题增强版
发布时间:2020-12-16 10:40:32 所属栏目:百科 来源:网络整理
导读:layout: post title: 八数码问题增强版 subtitle: c++ 八数码问题增强版 date: 2019-08-07 author: dainuofei header-img: img/post-bg-universe.jpg catalog: true tags: - BFS --- 题目描述 三行三列的数组,其元素值为0至8的数。现有如下的变换规则: 1:
layout: post 题目描述三行三列的数组,其元素值为0至8的数。现有如下的变换规则: 1: 将0与上面一行元素对换 2:将0与下面一行元素对换 3:将0与左面一行元素对换 4:将0与右面一行元素对换 如果已知一个三行三列元素的初始情况,问最少需几次变换,能变换为指定的一种情况? 输入包括六行的数据,每行有三个以空格分隔的数字。 前三行为原始状态 后三行为目标状态 输出若能在20次以内(包括20)变换得到目标状态的数组,输出最少的变换次数; 若不能在20次以内(包括20)变换得到目标状态的数组,输出No solution! 样例输入0 4 8 2 6 3 1 7 5 0 2 3 1 8 4 7 6 5 样例输出10 Hint(None) AC代码#include<iostream> #include <string.h> using namespace std; struct Point//结构体 { int a[3][3]; int step; }; Point s,t,q[50000]; int f,e; bool used[9][9][9][9][9][9][9][9];//used[][][][][][][][]是 Point gen(Point u,int type)//这个函数的主要内容就是枚举操作一遍所有的规则 跟 "倒水.cpp" 很相似 { int x,y; for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(u.a[i][j]==0) { x=i,y=j; break; } Point v=u; v.step=u.step+1; if(type==1&&x>0)//枚举第1种情况 swap(v.a[x][y],v.a[x-1][y]);//交换上面一行元素 else if(type==2&&x<2)//枚举第2种情况 swap(v.a[x][y],v.a[x+1][y]);//将0与下面一行元素对换 else if(type==3&&y>0)//枚举第3种情况 swap(v.a[x][y],v.a[x][y-1]);//将0与左面一行元素对换 else if(type==4&&y<2)//枚举第4种情况 swap(v.a[x][y],v.a[x][y+1]);//将0与右面一行元素对换 else v.step=-1;//如果交换不到指定的位置,就返回-1 return v; } bool cmp(Point u,Point v)//比较两个结构体是否相同,相同为True 不同为False { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(u.a[i][j]!=v.a[i][j]) return 0; return 1; } int main() { memset(used,sizeof(used));//used是 for(int i=0;i<3;i++)//输入初始矩阵 for(int j=0;j<3;j++) cin>> s.a[i][j]; for(int i=0;i<3;i++)//输入期望矩阵 for(int j=0;j<3;j++) cin>>t.a[i][j]; if(cmp(s,t)==1)//如果他们一样就不用移动 { cout<<0<<endl;//输出0步 return 0;//退出 } s.step=0;//初始化 f=1,e=1;//f出队 e入队 q[1]=s;//把s入队 used[s.a[0][0]][s.a[0][1]][s.a[0][2]][s.a[1][0]][s.a[1][1]][s.a[1][2]][s.a[2][0]][s.a[2][1]]=1;//把初始矩阵除了5以外的都标为已使用 while(f<=e)//防止越界 { Point u=q[f++];//u是选定的元素 for(int i=1;i<=4;i++)//像4个方向拓展 { Point v=gen(u,i);//v是由u按题目上的规则拓展而来的 if(v.step==-1) continue;//如果无法到达 if(v.step>20) continue;//如果大于20步 if(cmp(v,t)==1)//如果和预期的矩阵一样,就输出 { cout<<v.step<<endl;//输出 return 0; } if(v.step==20) continue;//如果等于20步 if (used[v.a[0][0]][v.a[0][1]][v.a[0][2]][v.a[1][0]][v.a[1][1]][v.a[1][2]][v.a[2][0]][v.a[2][1]]==1)//如果初始矩阵除了5以外的都走过 continue; e++;//入队下标+1 q[e]=v;//入队 used[v.a[0][0]][v.a[0][1]][v.a[0][2]][v.a[1][0]][v.a[1][1]][v.a[1][2]][v.a[2][0]][v.a[2][1]]=1;//把移完之后的状态保存,设为已经出现过 将来不能再出现 } } cout<<"No solution!"<<endl;//无解 return 0;//返回 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |