思维导图

例1：岛屿数量（medium）（深搜、宽搜）

用一个二维数组代表一张地图，这张地图由字符 " 0 " 与 " 1 " 组成，其中 " 0 " 代表水域， " 1 " 代表小岛。小岛 " 1 " 被水域 " 0 " 所包围，当 " 1 " 在水平和垂直方向相连接时，认为是同一块土地。求这张地图中小岛的数量。

• 算法思路 1 - DFS

1、标记当前搜索位置已被搜索。
2、按照方向数组的4个方向，拓展4个新位置。
3、若新位置不在地图范围内，则忽略
4、若新位置未曾到达过、且是陆地，继续DFS该位置。

• 算法思路 2 - BFS

1、设置搜索队列Q，标记mark[x][y]=1，并将待搜索位置push队列。
2、只要队列不空，即取队头元素，按照4个方向，拓展4个新位置。
3、若新位置不在地图范围内，则忽略。
4、若新位置未曾到达过、且是陆地，将该新位置push队列，并标记。

例2：词语阶梯（medium）（宽搜、图、哈希表）

已知两个单词（起始单词与结束单词），一个单词词典。
根据转换规则计算从起始单词到结束单词的最短转换步数。
转换规则：
1、在转换时，只能转换单词中的1个字符。
2、转换得到的新单词，必须在单词词典中。
例如：beginWord = "hit"，endWord = "cog"
wordList = ["hot"，"dot"，"dog"，"lot"，"'log"，"cog"]
最短转换方式："hit"->"hot"->"dot"->"dog"->"cog"，结果为5

• 算法思路 - BFS

给定起点，终点，图。
1、设置搜索队列Q，队列节点为pair<顶点，步数>；
设置集合visit，记录搜索过的顶点；将<beginWord，1>添加至队列；
2、只要队列不空，取出队列头部元素：
1）若取出的队列头部元素为endWord，返回到达当前节点的步数；
2）否则拓展该节点，将与该节点相邻的且未添加到visit中的节点与步数同时添加至队列Q，并将拓展节点加入visit；
3、若最终都无法搜索到endWord，返回0。

例3：词语阶梯2（hard）（记录路径的宽搜、图、哈希表）

1、在宽度优先搜索时，如何保存路径？
2、如果起始点与终点间有多条路径，如何将多条路径全部搜索出？

• 算法思路

1、到达某一位置可能存在多条路径，使用映射记录到达每个位置的最短需要的步数，新拓展到的位置只要未曾到达或到达步数与最短步数相同，即将该位置添加到队列中，从而存储了从不同前驱到达该位置的情况。
2、从所有结果（endWord）所在的队列位置（end-word pos），向前遍历直到起始单词（beginWord），遍历过程中，保存路径上的单词。如此遍历得到的路径为endWord到beginWord的路径，将其按从尾到头的顺序存储到最终结果中即可。

例4：火柴棍摆正方形（medium）（回溯深搜、位运算）

已知一个数，保存了n个（n<=15）火柴棍，问可否使这n个火柴摆1个正方形？

• 算法思路

1、想象正方形的4条边即为4个桶，将每个火柴杆回溯的放置在每个桶中。
2、放完后，检查4个桶中的火柴杆长和是否相同，相同返回真，否则返回假。
3、在回溯过程中，如果当前所有可能向后的回溯，都无法满足条件，返回假。
优化1：n个火柴杆的总和对4取余需要为0，否则返回假。
优化2：火柴杆按照从大到小的顺序排序，先尝试大的减少回溯可能。
优化3：每次放置时，每条边上不可放置超过总和的1/4长度的火柴杆。

例5：收集雨水（hard）（带优先级的宽度优先搜索、堆）

已知一个 m*n 的二维数组，数组存储正整数，代表一个个单元的高度，将这些立方体想象成水槽，问如果下雨这些立方体中会有多少积水。

• 算法思路

1、搜索队列使用优先级队列（堆），越低矮的点优先级越高（最小堆），越优先进行搜索。
2、以矩形四周的点作为起始点进行DFS（这些点要最初push进入队列）。
3、使用一个二维数组对push队列的点进行标记，之后搜索到该点后，不再push到队列中。
4、只要优先级队列不空，就取出队头元素进行搜索，按照四个方向进行拓展，拓展过程中忽略超出边界与已入队列的点。
5、当对某点（x，y，h）进行拓展时，得到的新点为（newx，newy，heightMap[newx][newy]）
如果 h>heightMap[newx][newy]：最终结果+= h-heightMap[newx][newy]，将heightMaplnewx][newy]赋值为h。
将（newx，newy，heightMap[newx][newy]）push优先级队列，并做标记。