最小基因变化

记住三种颜色：紫=正在访问（刚出队）、蓝=已入队待处理、绿=已访问完。队列先进先出，保证按层扩展，最短路径天然得到。

先把 6 个基因全摆上：点=基因，两基因只差一个字母就连边。还没开始搜，全是灰的，队列是空的。

起点 AACCGGTT 入队，记它在第 ① 层（自己到自己 0 次变化，层号从 1 起算）。队列：[AACCGGTT]。

从队头取出 AACCGGTT（标紫=正在访问），它在第 ① 层。逐个看它能一步变成哪些库里的基因。

AACCGGTT 改一个字母得到 AACCGGTA（库里有、没访问过），层号 = ① 的层 +1 = ②，入队。队列：[AACCGGTA]。

AACCGGTT 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。

从队头取出 AACCGGTA（标紫=正在访问），它在第 ② 层。逐个看它能一步变成哪些库里的基因。

AACCGGTA 改一个字母得到 AACCGCTA，正是目标 end！层号 = ② 的层 +1 = ③，入队。第一次碰到 end，最少变化次数就锁定 = 层号-1 = 2。

AACCGGTA 改一个字母得到 AAACGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA]。

AACCGGTA 改一个字母得到 AACGGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA, AACGGGTA]。

AACCGGTA 改一个字母得到 AAGCGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA, AACGGGTA, AAGCGGTA]。

AACCGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。

从队头取出 AACCGCTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。

AACCGCTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。

AACCGCTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。

从队头取出 AAACGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。

AAACGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。

AAACGGTA 也能一步变成 AAGCGGTA，但 AAGCGGTA 已经在队列里（更早入队），不重复入队。

AAACGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。

从队头取出 AACGGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。

AACGGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。

AACGGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。

从队头取出 AAGCGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。

AAGCGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。

AAGCGGTA 也能一步变成 AAACGGTA，但 AAACGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。

AAGCGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。

整张图按层扩完。最短变化链：AACCGGTT → AACCGGTA → AACCGCTA，相邻两基因都只差一个字母（一条边）。从起点到 end 共 2 条边，所以最少变化次数 = 2。

三个边界：起点即终点返 0；end 不在库直接 -1；搜空到不了也是 -1。

三个高频追问：为何用 BFS、怎么枚举邻居、双向 BFS 优化。