双向搜索

本节要介绍的不是

有 盏灯，每盏灯与若干盏灯相连，每盏灯上都有一个开关，如果按下一盏灯上的开关，这盏灯以及与之相连的所有灯的开关状态都会改变。一开始所有灯都是关着的，你需要将所有灯打开，求最小的按开关次数。

。

如果这道题暴力 DFS 找开关灯的状态，时间复杂度就是 , 显然超时。不过，如果我们用 meet in middle 的话，时间复杂度可以优化至 。meet in middle 就是让我们先找一半的状态，也就是找出只使用编号为 到 的开关能够到达的状态，再找出只使用另一半开关能到达的状态。如果前半段和后半段开启的灯互补，将这两段合并起来就得到了一种将所有灯打开的方案。具体实现时，可以把前半段的状态以及达到每种状态的最少按开关次数存储在 map 里面，搜索后半段时，每搜出一种方案，就把它与互补的第一段方案合并来更新答案。