05网格结构广度优先搜索
# 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)
上次更新: 2023/11/19, 12:55:48