什么是电子商务网站建设与管理,岐山网站建设,佛山网站建设外贸,做公司网站有什么好处给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合#xff0c;这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0#xff08;代表水#xff09;包围着。 岛屿的面积是岛上值为 1 的… 给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0代表水包围着。 岛屿的面积是岛上值为 1 的单元格的数目。 计算并返回 grid 中最大的岛屿面积。如果没有岛屿则返回面积为 0 。 输入grid [[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 输入grid [[0,0,0,0,0,0,0,0]] 输出0 提示
m grid.length n grid[i].length 1 m, n 50 grid[i][j] 为 0 或 1
解题思路
到过一处岛屿并感染dfs
代码
class Solution {public int maxres 0;public int res 0;public int maxAreaOfIsland(int[][] grid) {int len grid.length;int mar grid[0].length;for(int i 0; i len; i )for(int j 0; j mar; j )if(grid[i][j] 1) {res 0;dfs(grid, i, j, len, mar);maxres Math.max(maxres, res);}return maxres;}public void dfs(int a[][], int x, int y, int len, int mar) {a[x][y] 2;res ;int fx[] {-1, 1, 0, 0};int fy[] {0, 0, -1, 1};int fxx 0, fyy 0;for(int i 0; i 4; i ) {fxx x fx[i];fyy y fy[i];if(fxx 0 fxx len fyy 0 fyy mar a[fxx][fyy] 1) dfs(a, fxx, fyy, len, mar);}}
}
