一、簡介

最小步數(shù)模型和最短路模型的區(qū)別？

最短路模型：某一個(gè)點(diǎn)到另一個(gè)點(diǎn)的最短距離（坐標(biāo)與坐標(biāo)之間）

最小步數(shù)模型：不再是點(diǎn)（坐標(biāo)），而是狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)變

BFS難點(diǎn)所在（最短路問題）：

1. 存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列

狀態(tài)如何存儲(chǔ)到隊(duì)列里邊（以什么形式）?
2. 狀態(tài)怎么表示，怎么轉(zhuǎn)移?

1. dist

如何記錄每一個(gè)狀態(tài)的距離

**技巧：**在最小步數(shù)模型中狀態(tài)和狀態(tài)的距離通常用哈希表來進(jìn)行存儲(chǔ)（存在key-value的映射關(guān)系?。?，如map，unordered_map。

**思路：**將初始狀態(tài)加入隊(duì)列，然后去搜索擴(kuò)展，直到搜索到目標(biāo)狀態(tài)為止。

注：

在搜索過程中可能由狀態(tài)的切換，如一維坐標(biāo)切換到二維坐標(biāo)，字符串切換到二標(biāo)坐標(biāo)形式的狀態(tài)等等！

技巧：一維數(shù)組與二維數(shù)組坐標(biāo)的轉(zhuǎn)換

設(shè)[一維數(shù)組]下標(biāo)為index（從0開始），二維數(shù)組長度為m * n，則：

一維數(shù)組轉(zhuǎn)換為二維數(shù)組

x = index / n?

y = index % n

二維數(shù)組轉(zhuǎn)換為一維數(shù)組

index = x + y * n

**技巧：**在最小步數(shù)模型中狀態(tài)和狀態(tài)的距離通常用哈希表來進(jìn)行存儲(chǔ)（存在key-value的映射關(guān)系?。?，如map，unordered_map。

**技巧：**BFS存儲(chǔ)路徑問題，通常通過設(shè)置一個(gè)前驅(qū)pre數(shù)組來記錄當(dāng)前節(jié)點(diǎn)或者狀態(tài)的前驅(qū)，最后再逆推找出路徑