一、简介

最小步数模型和最短路模型的区别？

最短路模型：某一个点到另一个点的最短距离（坐标与坐标之间）

最小步数模型：不再是点（坐标），而是状态到另一个状态的转变

BFS难点所在（最短路问题）：

1. 存储的数据结构：队列

状态如何存储到队列里边（以什么形式）?
2. 状态怎么表示，怎么转移?

1. dist

如何记录每一个状态的距离

**技巧：**在最小步数模型中状态和状态的距离通常用哈希表来进行存储（存在key-value的映射关系！），如map，unordered_map。

**思路：**将初始状态加入队列，然后去搜索扩展，直到搜索到目标状态为止。

注：

在搜索过程中可能由状态的切换，如一维坐标切换到二维坐标，字符串切换到二标坐标形式的状态等等！

技巧：一维数组与二维数组坐标的转换

设[一维数组]下标为index（从0开始），二维数组长度为m * n，则：

一维数组转换为二维数组

x = index / n 

y = index % n

二维数组转换为一维数组

index = x + y * n

**技巧：**在最小步数模型中状态和状态的距离通常用哈希表来进行存储（存在key-value的映射关系！），如map，unordered_map。

**技巧：**BFS存储路径问题，通常通过设置一个前驱pre数组来记录当前节点或者状态的前驱，最后再逆推找出路径