大佬教程收集整理的这篇文章主要介绍了c++ 八数码问题增强版,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
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: 将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
(NonE)
#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;//返回 }
以上是大佬教程为你收集整理的c++ 八数码问题增强版全部内容,希望文章能够帮你解决c++ 八数码问题增强版所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。