币圈小鱼儿
【鲸交所靠谱吗】BFS 和 DFS 两种方式求岛屿的最大面积
来源：数据结构和算法 / 山大王 wld
问题描述
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个岛屿是由一些相邻的 1(代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0 （代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵 , 返回 0。
注意 : 给定的矩阵 grid 的长度和宽度都不超过 50。
DFS 解决
这题无论使用 DFS 还是 BFS 都很好解决，DFS 就是沿着一个方向一直走下去，直到不满足条件为止（要么走出 grid 的边缘，要么当前位置是 0），就像下面这样，
代码如下
1public int maxAreaOfIsland(int[][] grid) { 2 int maxArea = 0; 3 for (int i = 0; i < grid.length; i++) 4 for (int j = 0; j < grid[0].length; j++) 5 if (grid[i][j] == 1) {// 如果当前位置是 1，开始计算 6 maxArea = Math.max(maxArea, dfs(grid, i, j)); 7 } 8 return maxArea; 9} 10 11public int dfs(int[][] grid, int i, int j) { 12 // 边界条件的判断 13 if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1) { 14 // 当前位置如果是 1，为了防止重复计算就把他置为 0，然后再从他的上下左右四个方向开始查找 15 grid[i][j] = 0; 16 return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1); 17 } 18 return 0; 19}
BFS 解决
BFS 我们可以使用一个队列来实现，他的实现原理就是如果一个位置是 1，我们就把他上下左右为 1 的点的坐标全部加入到队列中，然后改变当前位置的坐标为 0，防止重复计算。加入队列之后再一个个出队，然后再以出队的那个点重复上面的操作……，直到队列为空为止。就像下面这样，假如遍历到红色的 1，我们就把他上下左右为 1 的位置坐标全部加入到队列中。
1public int maxAreaOfIsland(int[][] grid) { 2 int maxArea = 0; 3 for (int i = 0; i < grid.length; i++) 4 for (int j = 0; j < grid[0].length; j++) 5 if (grid[i][j] == 1) {// 如果当前位置是 1，开始计算 6 maxArea = Math.max(maxArea, bfs(grid, i, j)); 7 } 8 return maxArea; 9} 10 11public int bfs(int[][] grid, int i, int j) { 12 int m = grid.length, n = grid[0].length; 13 if (grid[i][j] == 0) 14 return 0; 15 grid[i][j] = 0; 16 // 队列中存储的是个二维数组，这个二维数组就是格子的坐标 17 Queue<int[]> queue = new LinkedList<>(); 18 //offer 表示添加到队列的末尾 19 queue.offer(new int[]{i, j}); 20 // 分别表示右，左，下，上，四个方向 21 int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 22 int res = 1; 23 while (!queue.isEmpty()) { 24 //poll 表示从队列的头部移除一个元素 25 int[] pos = queue.poll(); 26 // 然后从 pos 坐标的 4 个方向再分别查找 27 for (int[] dir : dirs) { 28 int x = dir[0] + pos[0]; 29 int y = dir[1] + pos[1]; 30 // 边界条件的判断 31 if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) { 32 continue; 33 } 34 grid[x][y] = 0; 35 res++; 36 queue.offer(new int[]{x, y}); 37 } 38 } 39 return res; 40}
总结
如果对图的遍历比较了解的话，这两种方式很容易想到，一个是沿着一个方向一直走下去，一个就像波浪一样，沿着一个点然后往四周一圈一圈的发散。
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：juu3644。
