C++ 实例之九宫格广度优先遍历
2019/7/10 22:48:03
本文主要是介绍C++ 实例之九宫格广度优先遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
C++ 实例之九宫格广度优先遍历
基本思路:
广度优先遍历,每次找到1的位置,分别向上、向下、向左、向右移动。把移动后的每个状态存储到队列中,弹出队头,判断是否为最终结果状态,如果是,输出遍历的层数(即移动步数),如果不是,把现阶段状态继续执行找到1向上向下向左向右移动操作。
#include<stdio.h> typedef struct MyType { int number[3][3];int level; }MyType; MyType queue[10000]; MyType GetHead(int n) { return queue[n]; } //是否为最终结果状态 int IsFind(MyType cur) { int flag=1; for(int i=0;i<3;i++) for(int j=0;j<3;j++) { if(cur.number[i][j]!=3*i+j+1) { flag=0; break; } } return flag; } int main() { int cnt=0;//队列中数量 int flag=0;//是否寻找到标记 int ans=0;//最小步数,也是扩展的层数 int head=0;//因为不是链表,用head来表示第一个 for(int m=0;m<3;m++) { for(int n=0;n<3;n++) { scanf("%d",&queue[cnt].number[m][n]); } } queue[cnt].level=0; cnt++; while(cnt!=0) { //出站 MyType cur=GetHead(head++); //判断是否为最终状态 flag=IsFind(cur); if(flag==1) { printf("最小步数为:%d\n",cur.level); break; } else //不为最终状态,进行扩展 { for(int row=0;row<3;row++) for(int col=0;col<3;col++) { if(cur.number[row][col]==1) //找到1,进行扩展 { //将1向上移 if(row!=0) { MyType temp=cur; temp.number[row][col]=temp.number[row-1][col]; temp.number[row-1][col]=1; temp.level=cur.level+1; queue[cnt++]=temp; } //将1向右移动 if(col!=2) { MyType temp=cur; temp.number[row][col]=temp.number[row][col+1]; temp.number[row][col+1]=1; temp.level=cur.level+1; queue[cnt++]=temp; } //将1向下移动 if(row!=2) { MyType temp=cur; temp.number[row][col]=temp.number[row+1][col]; temp.number[row+1][col]=1; temp.level=cur.level+1; queue[cnt++]=temp; } //将1向左移动 if(col!=0) { MyType temp=cur; temp.number[row][col]=temp.number[row][col-1]; temp.number[row][col-1]=1; temp.level=cur.level+1; queue[cnt++]=temp; } } } } } return 0; }
有个问题,就是还没弄懂,怎么判断给定初始状态无解,即不可能到达最终结果状态??
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
这篇关于C++ 实例之九宫格广度优先遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-07Dify + TiDB Vector,快速构建你的AI Agent
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享