租服务器发布网站,django 网站开发教程,都匀网站制作公司,做家具网站这是C算法基础-搜索与图论专栏的第X篇文章#xff0c;专栏详情请见此处。 引入 上篇博客#xff0c;我们学习了BFS算法的大体套路#xff0c;这次#xff0c;我将会通过两个例题来更详细的讲解。 下面我们就来讲BFS算法#xff08;例题#xff09;的实现。
过程 例题1算法基础-搜索与图论专栏的第X篇文章专栏详情请见此处。 引入 上篇博客我们学习了BFS算法的大体套路这次我将会通过两个例题来更详细的讲解。 下面我们就来讲BFS算法例题的实现。
过程 例题1走迷宫 题目大意给定一个二维整数数组用来表示一个迷宫数组中只包含0或1其中0表示可以走的路1表示不可通过的墙壁。若一个人从左上角出发每次可以向周围四个位置移动一格要移动至右下角处最少需要移动多少次。 若该题目问的是是否能到达终点那么用DFS算法就可以了但此题要求最小移动步数就需要考虑BFS算法的路径最短的特点了。 我们从起点开始往前走第一步记录下所有第一步能走到的点然后从所第一步能走到的点开始往前走第二步记录下所有第二步能走到的点重复下去直到走到终点此时可以肯定的是当前的步数一定最短输出即可。 例题2八数码 题目大意在一个3×3的网格中1~8这8个数字和一个“x”恰好不重不漏地分布在这3*3的网格中。 在游戏过程中可以把“x”与其上、下、左、右四个方向之一的数字交换如果存在。 我们的目的是通过交换使得网格变为如下排列称为正确排列 1 2 3 4 5 6 7 8 x 请你求出得到正确排列最少需要进行多少次交换。 玩过华容道的人都知道这是很简单的3*3的数字华容道游戏现实生活中肯定很多人都能做出来。但放到C中乍一看好像没什么思路但此题要求得出最优答案所以选择BFS算法。 很重要的一点是我们可以把游戏中的移动数字视为移动空格“x”这样做的好处是操作由移动八个数字变为移动一个空格。空格从起点开始往前走第一步记录下所有第一步走过后的状态然后从所第一步走到了的点开始往前走第二步记录下所有第二步走过后的状态重复下去直到达到目标状态得出最优答案输出即可。 这里的一个实现困难就是二维数组的处理实际上我们可以将矩阵转换为字符串下标需从0开始对字符串进行处理其中转换公式为下标x*3y、x下标/3、y下标%3、左移下标-1、右移下标1、上移下标-3、下移下标3。 上一篇- C算法基础专栏文章 下一篇- 每周六更新一篇文章内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞关注一下呗~
