大家好，阿清今天继续给大家分享关于算法的代码总结，这一次，咱们聊深度优先搜索与广度优先搜索。
这两种搜索算法也算是经常出现在面试的算法题中。
今天，阿清主要想和大家分享的是以二维数组为载体的深度优先搜索算法与广度优先搜索算法，因为这类题型十分常见。
依据leetcode中的算法题，一般都是用二维数组来表达一个范围，且通过二维数组中的每个位置上元素的值表达一些含义，
接着对一些相邻的位置做文章。
这样的题型，我们便可考虑使用深度优先搜索与广度优先搜索来完成。
01
—
深度优先搜索
废话不多说，我们直接上模板。
class Solution {
// 这两个数组用来确定搜索的方向
// 例如:当前元素grid[r][c]
// 则 grid[r + dr[0]][c + dc[0]] 表示 当前元素上边的元素
// grid[r + dr[1]][c + dc[1]] 表示 当前元素左边的元素
private int[] dr = new int[]{-1, 0, 1, 0};
private int[] dc = new int[]{0, -1, 0, 1};
// 函数的类型，这里暂时写为int，因为大多数遍历最后的结果都是一个数字
public int handle(int[][] grid) {
if (grid == null ||grid.length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
for (int r = 0; r < row; ++r) {
for (int c = 0; c < col; ++c) {
// 依据题意的条件，进入深度优先搜索
if (...) {
dfs(grid, r, c, ...);
}
}
}
// 针对题意，也许需要写一些判断的逻辑，或直接返回结果
...
}
// 传入的参数中，grid、r、c 这三个用来定位二维数组中的某个元素
// 但并不局限于上述三个参数
private void dfs(int[][] grid, int r, int c, ... ) {
if (isOutBoundary) {
return;
}
//依据题意，写出一些针对grid[r][c]的处理或判断
...
// 遍历该元素四周的元素
for (int n = 0; n != 4; ++n) {
int nr = r + dr[n];
int nc = c + dc[n];
dfs(grid, nr, nc, ...);
}
}
// 用于判断该元素是否超出了二维数组的范围
private boolean isOutBoundary(int[][] grid, int r, int c) {
return r < 0 || r == grid.length || c < 0 || c == grid[0].length;
}
}
上述模板中 省略号的位置，则是自己依据题意去编写一些符合题意的特定代码。
可以看到，深度优先搜索使用了递归。
大家重点关注dfs方法两个地方。
第一处，就是传入的参数，可以依据题意传入一些其他的参数。
第二处，即对依据grid[r][c]
的值做出的一些处理。
02
—
广度优先搜索
还是直接上模板，在广度优先搜索中，我们将用到队列。
class Solution {
// 同深度优先搜索一样，需要方向数组来向元素的四周遍历
int[] dr = new int[] {-1,0,1,0};
int[] dc = new int[] {0,-1,0,1};
// 同样的，这里方法的返回类型暂时写为int
public int handle(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
// 大部分题目，也许会声明一些结果变量
int count = 0;
// 用于存放元素的队列
Queue<Integer> queue = new ArrayDeque();
for (int r = 0; r < row; ++r) {
for (int c = 0; c < col; ++c) {
// 依据题意的条件，初始化遍历队列
if(...) {
// 将元素的位置转换为一维数组坐标
int code = r*col + c;
// 塞进队列里
queue.add(code);
int res = bfs(queue, grid);
// 这里的f方法代表会将count 与 res 做一些比较，以维护最新的满足题意的结果
// 如f可以是 Math.min 或者 Math.max 或者 所示 count + res 等
count = f(count, res);
}
}
}
return count;
}
private int bfs(Queue<Integer> queue, int[] grid) {
// 这里声明一个res参数，因为在搜索的过程，一般会进行统计之类的任务
int res = 0;
while(!queue.isEmpty()) {
int code = queue.remove();
// 将一维坐标转化为二维坐标
int r = code/Column, c = code%Column;
for(int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
// 依据题意，除了保证遍历的位置在二维数组内部，同时也可编写其他的条件
if(!isOutBoundary && ...) {
// 依据题意 写出对当前元素的处理, 并更新res
...
// 将四周的元素继续塞进队列里
int ncode = nr*Column + nc;
queue.add(ncode);
}
}
}
return res;
}
// 用于判断该元素是否超出了二维数组的范围
private boolean isOutBoundary(int[][] grid, int r, int c) {
return r < 0 || r == grid.length || c < 0 || c == grid[0].length;
}
}
广度优先搜索算法的关键就在于遍历队列时，
在遍历到符合条件的元素后，对当前这个元素所做的处理，以及对一些统计变量的更新。
最后，在完成所有的遍历后，得到一个满足题意的全局最值。
03
—
总结
阿清今天主要向大家介绍基于二维数组模型的深度优先搜索算法与广度优先搜索算法。
其中，深度优先搜索算法会用到递归，广度优先搜索算法会用到队列。
它们的共同点：
1、都会用到方向数组，向四个方向进行遍历。
2、都会判断元素位置是否超出二维数组的边界。
3、都可以从一个双重循环，即从二维数组的第一个元素（grid[0][0]
）进入搜索算法。
阿清在文章末尾，给大家找了两道leetcode题，这两道题都可以使用上面这两种方法，供小伙伴们练习参考。
腐烂的橘子：
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
腐烂的橘子 https://leetcode.cn/problems/rotting-oranges/
岛屿的最大面积：
给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
岛屿的最大面积：https://leetcode.cn/problems/max-area-of-island/
关注六只栗子，面试不迷路~
作者 阿清
编辑 一口栗子
