洛谷 P1032 [NOIP 2002 提高组] 字串变换
本题采用双向 BFS 来解决。 首先分析一下时间复杂度：变换规则数 R≤6R \leq 6R≤6 ，字符串长度 L≤20L \leq 20L≤20，操作数在 10 次以内，用朴素 BFS 的时间复杂度为 O((L⋅R)10)O((L\cdot R)^{10})O((L⋅R)10) ，完全爆炸；采用双向 BFS 的时间复杂度为 O((L⋅R)5)O((L\cdot R)^{5})O((L⋅R)5) ，相对于朴素做法降低了很多的时间复杂度。 但对于本题，可能出现以下情况：每次变换可能在字符串的多个位置替换、变换规则可能形成“无限繁殖”的状态等，导致搜索空间飞速增长。双向 BFS 并不能保证通过本题的数据，但也是一种优化搜索的方法。 双向 BFS 的具体步骤： 开两个队列 qa,qbqa,qbqa,qb，一开始分别把起点和终点丢入队列中。 每次选择较小的队列进行扩展，将队头其可能经过变换规则得到的字符串丢入队列中（注意假如扩展 qbqbqb...
洛谷 P9243 蓝桥杯 2023 省B 岛屿个数
本题要求求一个地图中的岛屿数量，但是不包括子岛屿（在其它岛屿围成的环之间）。 对于求岛屿，可以使用搜索中的 Flood Fill 算法来实现，对每个为 111 的陆地进行 BFS，标记与它相邻的所有陆地。为了实现环内部的岛屿不被统计，我们可以先 BFS 海域，在 BFS 海域的过程中如果遍历到为 111 的陆地，就来一遍 Flood Fill 将其相邻的陆地全部打上标记，如果遍历到为 000 的海水就不入队（只有 000 会入队）。 需要注意的是，遍历海域是八个方向拓展的，而遍历陆地是四个方向扩展的。同时我们能保证海水拓展八个方向得到的岛屿都不在环内，这是因为陆地不入队，岛屿在环内的话是进不去的。可以借助下面样例来理解： 123450111111001101011000111111 我们不可能遍历到 (3,2)(3,2)(3,2) 位置的 000 的，因为 000 不入队，遍历海域是进不到环内的，自然就遍历不到环内的 111 了。所以我们对于每次 Flood Fill，直接将答案加 111...