LeetCode 752打开转盘锁：两种BFS实现为何一者TLE一者通过

出队时标记访问导致TLE的核心逻辑 #

最初的实现将节点加入visited集合的操作放在节点出队阶段，会引发严重的重复入队问题，这是超时的直接原因：

• 转盘锁的每个状态最多有8个相邻状态（4个转盘，每个可上下拨1位），同一个中间状态可以被多个不同的上层状态抵达。比如状态0001，既可以从起点0000拨第一位得到，也可以从0011拨第二位、0101拨第三位、1001拨第四位等多个路径抵达。
• 由于节点只有出队时才会被标记为已访问，在它排队等待出队的整个周期里，所有能走到它的上层节点遍历邻接节点时，都会判定它「未访问、不在死亡列表」，于是会把同一个节点重复加入队列多次。
• 转盘锁总共只有10^4 = 10000种可能的状态，但第一种实现的队列中会塞入远大于10000的重复节点。随着BFS层数加深，重复入队的节点数呈指数级增长，队列弹出、邻接节点遍历的开销会快速爆炸。提到的目标为8888的测试用例中，BFS需要走8层才能到目标，中间层节点的重复入队会让队列长度膨胀到数十万级，直接触发时间限制。

入队时标记访问能通过用例的原因 #

修改后的实现将visited.add(nb)放在邻接节点首次被发现、准备入队的时机，从根源上杜绝了重复入队：

• 任意节点第一次被上层节点遍历到时，就会立刻被标记为已访问再加入队列。后续其他上层节点再遍历到这个节点时，会直接因为「已存在于visited集合」被跳过，不会重复入队。
• 这种实现下，队列中存储的节点总数最多就是全部有效状态数（上限10000个），没有任何冗余重复节点，BFS时间复杂度稳定在常数级（总状态数固定为1万），运行效率极高，自然可以通过全部测试用例。

注意：BFS算法的标准实现规范就是节点入队时立刻标记为已访问，如果延后到出队阶段再标记，本质是推迟了去重时机，会产生大量无效计算，在状态空间稍大的搜索类题目中几乎必然超时。

内容的提问来源于stack exchange，提问作者Victor Cui