最小基因变化 (Minimum Genetic Mutation)

1. 题目描述

题目背景： 在生物信息学中，基因序列的演变可以抽象为字符串的变换问题。本题考察在给定的“合法状态库”约束下，寻找从初始状态到目标状态的最短路径。这在 NOI 竞赛中属于典型的隐式图最短路问题。

任务描述： 基因序列可以表示为一条由 8 个字符组成的字符串，字符只包含 'A'、'C'、'G' 和 'T'。 假设我们需要调查从基因序列 startGene 到 endGene 的变化，一次基因变化定义为将基因序列中的一个字符替换为另一个字符。

• 例如，"AACCGGTT" -> "AACCGGTA" 是一次基因变化。

此外，还有一个基因库 bank，记录了所有有效的基因变化。只有变化后的基因序列出现在 bank 中，这次变化才算有效。 请你计算从 startGene 变化到 endGene 所需的最少变化次数。如果无法完成变化，返回 -1。

输入格式：

1. 第一行包含一个长度为 8 的字符串，表示 startGene。
2. 第二行包含一个长度为 8 的字符串，表示 endGene。
3. 第三行包含一个整数 $m$（$0 \le m \le 10$），表示基因库 bank 中的序列数量。
4. 接下来的 $m$ 行，每行包含一个长度为 8 的字符串，表示基因库中的一个有效基因。

输出格式： 一个整数，表示最少变化次数。

样例 1： 输入：

AACCGGTT
AACCGGTA
1
AACCGGTA

输出：

1

样例 2： 输入：

AACCGGTT
AAACGGTA
3
AACCGGTA
AACCGCTA
AAACGGTA

输出：

2

样例 3： 输入：

AAAAACCC
AAAAACCC
0

输出：

0

2. 预备知识点

1. 宽度优先搜索 (BFS)：在无权图中寻找从起点到终点的最短路径（步数最少）。
2. 状态空间搜索：将每个基因序列看作图的一个节点，如果两个序列仅差一个字符且都在基因库中，则它们之间存在一条边。
3. 字符串处理与哈希：使用 std::set 或 std::unordered_set 快速判断一个基因序列是否在 bank 中。
4. 去重处理：使用 visited 集合记录已搜索过的状态，避免陷入死循环或重复计算。

3. 启发式思维引导

请拿出草稿纸，跟随教练的思路，一步步写出推导过程。

第一步：图论抽象

• 节点：每一个长度为 8 的基因字符串。
• 边：如果字符串 A 改变 1 个字符能变成字符串 B，且 B 在 bank 中，则 A 连向 B。
• 目标：寻找从起点到终点的最短路径长度。
• 思考：为什么要用 BFS 而不是 DFS？
• 结论：BFS 具有“层序遍历”特性，第一遍搜到终点时，所经过的层数一定是最小步数。

第二步：状态转移枚举

对于当前的基因序列（长度为 8），我们要尝试所有可能的“下一步”：

1. 遍历序列的每一个位置（0 到 7）。
2. 在每个位置上，尝试将其替换为 'A', 'C', 'G', 'T' 中除原字符外的其他 3 个字符。
3. 构造出新字符串后，去 bank 中检查它是否合法。

第三步：复杂度分析（在草稿纸上估算）

• 时间复杂度：
  • 状态总数受限于 bank 大小 $M$。
  • 每个状态尝试 $8 \times 3 = 24$ 次变化。
  • 字符串比对耗时 $L=8$。
  • 总复杂度约 $O(M \cdot L \cdot |\Sigma|)$，其中 $|\Sigma|=4$。对于 $M=10$ 的规模，计算量极小。
• 空间复杂度：
  • 需要存储 bank 和 visited 集合，空间复杂度 $O(M \cdot L)$。

4. 算法流程图 (C++14 逻辑提示)

graph TD
    Start(开始) --> Input(读入 startGene, endGene, bank)
    Input --> BankSet(将 bank 存入 set 方便查找)
    BankSet --> InitCheck{start 等于 end 吗}
    InitCheck -- 是 --> Return0(输出 0 并结束)
    InitCheck -- 否 --> QueueInit(初始化队列 Q: 存入对 start, 0)
    QueueInit --> VisitInit(初始化 visited 集合: 存入 start)
    
    QueueInit --> WhileQ{Q 是否为空}
    WhileQ -- 是 --> ReturnFail(输出 -1)
    WhileQ -- 否 --> Pop(弹出队首 currGene, step)
    
    Pop --> LoopPos(遍历字符串 8 个位置 i)
    LoopPos --> LoopChar(尝试替换为 ACGT 中的字符 c)
    LoopChar --> NewGene(构造新基因 nextGene)
    
    NewGene --> CheckValid{nextGene 在 bank 中且未访问吗}
    CheckValid -- 否 --> LoopChar
    CheckValid -- 是 --> CheckEnd{nextGene 等于 endGene 吗}
    
    CheckEnd -- 是 --> ReturnAns(输出 step + 1 并结束)
    CheckEnd -- 否 --> PushQ(将 nextGene, step + 1 入队并标记访问)
    PushQ --> LoopChar
    
    LoopChar -- 字母试完 --> LoopPos
    LoopPos -- 位置跑完 --> WhileQ

5. 读题关键词总结

在 NOI 读题中，看到以下关键词要形成“肌肉记忆”：

1. “最少变化次数” (Minimum Steps)：
   • 核心算法：BFS（宽度优先搜索）。
2. “有效基因库” (Valid Bank/Constraint)：
   • 实现技巧：在 BFS 扩散时，先判断 if (bankSet.count(nextGene))。
3. “只有 1 个字符不同” (Mutation/Edit Distance 1)：
   • 实现技巧：通过两层嵌套循环（位置 + 字符）来主动生成邻居节点。
4. “长度固定为 8”：
   • 意义：常数较小，意味着你可以进行相对耗时的字符串操作（如直接拷贝字符串）而不用担心超时。
5. “无法完成变化返回 -1”：
   • 实现技巧：BFS 队列为空后仍未找到目标，则输出 -1。

教练点评： 本题是典型的“隐式图”搜索题。在考场上，注意处理起始基因和目标基因相同的情况（样例 3），以及目标基因不在基因库中的情况。利用 std::unordered_set 可以让查找更高效，但在 $M=10$ 的情况下，普通的 std::set 甚至 std::vector 遍历也绰绰有余。加油！