简介:
先走到A,之后弹出A再把A能走到的地方加进去向外扩展把队列里面的元素(B,C)弹出来,再把B,C能到的地方入队列
一直这样那么最短路程就是扩展的层数。
迷宫中离入口最近的出口(medium):
题目链接:1926. 迷宫中离入口最近的出口 - 力扣(LeetCode)
算法:
利用层序遍历来解决迷宫问题,是最经典的做法。
我们可以从起点开始层序遍历,并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候,得到起点到出⼝的最短距离。
最小基因变化(medium):
题目链接:433. 最小基因变化 - 力扣(LeetCode)
算法:
如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话,问题就变成了「边权为 1的最短路问题」。
因此,从起始的字符串开始,来⼀次 bfs 即可。


单词接龙(hard):
题目链接:127. 单词接龙 - 力扣(LeetCode)
算法:
跟上题⼀样~
为高尔夫比赛砍树(hard):
题目链接:675. 为高尔夫比赛砍树 - 力扣(LeetCode)
算法:
- 先找出砍树的顺序;
- 然后按照砍树的顺序,⼀个⼀个的用bfs 求出最短路即可。