05 网格结构广度优先搜索

广度优先搜索简介

深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。

二维数组深度优先搜索的一般写法：

​ 一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否满足开始搜索的条件，如果可以即在辅函数中进行搜索。

​ 辅函数负责实现深度优先搜索过程。这一过程可以使用递归调用调用实现；当然，我们也可以使用栈（stack）实现深度优先搜索，与使用队列 （queue）实现广度优先搜索类比。但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时推荐使用递归式写法，可以将深度优先搜索与回溯算法进行类比。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。

​ 在辅函数里，一个一定要注意的点是辅函数内递归搜索时，对矩阵边界条件的判定。边界判定一般有两种写法：一种是先判定是否越界，只有在合法的情况下才进行下一步搜索（即判断放在调用递归函数前）；另一种是不管三七二十一先进行下一步搜索，待下一步搜索开始时再判断是否合法（即判断放在辅函数第一行）。两种方法任选一种符合自身代码习惯的写法即可。

​ 二维数组四向遍历小技巧：对于四个方向的遍历，可以创造一个数组 direction = [-1, 0, 1, 0, -1]，每相邻两位即为上下左右四个方向之一，即：

• 左移 x+=direction[0]; y+=direction[1]；
• 上移 x+=direction[1]; y+=direction[2]；
• 右移 x+=direction[2]; y+=direction[3]；
• 下移 x+=direction[3]; y+=direction[4]；

542 0-1 矩阵 (opens new window)

130 被围绕的区域 (opens new window)

934 最短的桥 (opens new window)

126 单词接龙 II (opens new window)

994 腐烂的橘子 (opens new window)