本人现在沉迷刷题无法自拔，生活中再也找不到其他乐趣了，甚至以为今天已经大年初一了：

被朋友这么一提醒，真的是哭笑不得😭😭。 whatever，不管是大年初一还是但年三十，今天反正是被下面这道看起来并不难的题给折磨到了：

1345. 跳跃游戏 IV

不难想到，这道题可以转换为「无权图最短路径」问题，然后用 BFS 策略解决。

难就难在，直接建图并 BFS，会超时。BFS 的时间复杂度为 $O(V+E)$，其中 $V$、$E$ 分别代表图的顶点数和边数。对于这道题，边数最坏为 $O(n^2)$，所以时间复杂度最坏也是 $O(n^2)$，此时数组中所有数都相等。这道题限制 $n<=5\times 10^4$，所以直接用经典 BFS 是肯定会超时的。

我一开始被卡在在这个用例：

$7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7\dots \dots 11$

其中省略号为很多个 $7$。

然后我尝试优化了一下，把连等的若过个数当成一个数，结果又被卡在了下面的用例上：

$1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,\dots \dots ,7,11$

其中省略号为很多个 $1,2$。太磨人了😭

最后无奈看了官解。发现采取了一种过河拆桥策略：先用一个哈希表存储每组相等数字的下标；任一组相等的数字，都构成了一个稠密子图，只要发现这个稠密子图的第一个下标，就将剩下的所有下标入队列，并且将该组从哈希表中抹去。

这个过河过河拆桥策略非容易用代码实现，但是我怎么也理解不了其正确性。我把前两页的题解都翻着看了一遍，发现大部分题解都和官解的思路一致，但基本都是直接上代码，没有解释其原理。宫水三叶的题解有论述这个策略的正确性，可惜我看不懂。

也许是这个原理太简单了，对大多数人都是自明的，只是我太笨，或者钻牛角尖了🤣

下午的时候我终于理解了，但是我发现很难用语言表达出来。哪位大佬能通俗易懂地解释一下？

而且这个题，居然还是一个系列，一二三四五六七八都有，比葫芦娃还多：