岛屿的最大面积

àì夳堔傛蜴生んèń 2022-01-21 08:51 219阅读 0赞

## 1、题目描述 ##

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为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。

## 2、解法 ##

### 2.1 DFS（深度优先遍历） ###

int m ;
    	int n ;
    	
    	int[][] around = { { 0,1},{ 1,0},{ 0,-1},{ -1,0}};
    	
    	public int maxAreaOfIsland(int[][] grid) { 
    		m = grid.length;
    		n = grid[0].length;
    		
    		int maxArea=0;
    		for(int i=0;i<m;i++) { 
    			for(int j=0;j<n;j++) { 
    				maxArea = Math.max(maxArea, dfs(grid, i,j));
    			}
    		}
    		return maxArea;
        }
    	
    	/** * 深度遍历，计算某点的周围为1的节点的数量 * @param grid * @param i * @param j * @return */
    	private int dfs(int[][]grid, int i, int j) { 
    		if(i<0|| i>=m || j<0||j>=n || grid[i][j] ==0) { 
    			return 0;
    		}
    		int area =1;
    		grid[i][j]=0;
    		
    		for(int[] arr:around) { 
    			area +=dfs(grid, i+arr[0], j+arr[1]);
    		}
    		return area;
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关 695. 岛屿的最大面积

695. 岛屿的最大面积给你一个大小为 m x n 的二进制矩阵 grid 。岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在

古城微笑少年丶/ 2024年03月31日 08:50/ 0 赞/ 77 阅读

相关 leetcode695. 岛屿的最大面积

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

Love The Way You Lie/ 2024年03月26日 10:39/ 0 赞/ 70 阅读

相关 leetcode 695. 岛屿的最大面积

bfs即可。不过需要注意，leetcode的判题系统是并发的执行样例，所以使用全局变量可能会出错。 int dx[4]={1,-1,0,0}; int dy[

叁歲伎倆/ 2023年07月15日 02:49/ 0 赞/ 50 阅读

相关岛屿的最大面积

一、前言问题来源LeetCode 问题链接：[https://leetcode-cn.com/explore/interview/card/bytedance/243

约定不等于承诺〃/ 2023年02月19日 09:26/ 0 赞/ 20 阅读

相关【LeetCode】岛屿（周长、数量、最大面积、封闭岛屿数）

文章目录岛屿的周长★ 岛屿数量★★ 岛屿数量Ⅱ★★★ 岛屿的最大面积★★

た入场券/ 2023年01月06日 01:57/ 0 赞/ 153 阅读

相关 695. 岛屿的最大面积

> 给定一个包含了一些 0 和 1 的非空二维数组 grid 。 > > 一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者

灰太狼/ 2022年10月08日 05:44/ 0 赞/ 170 阅读

相关 Leetcode 695. 岛屿的最大面积

题目重述给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平

青旅半醒/ 2022年09月08日 12:55/ 0 赞/ 187 阅读

相关 leetcode 695. 岛屿的最大面积python

给定一个包含了一些 0 和 1的非空二维数组 `grid` , 一个岛屿是由四个方向 (水平或垂直) 的 `1` (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被

浅浅的花香味﹌/ 2022年05月13日 16:27/ 0 赞/ 245 阅读

相关岛屿的最大面积

1、题目描述给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的

àì夳堔傛蜴生んèń/ 2022年01月21日 08:51/ 0 赞/ 220 阅读

相关 695. 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着

迷南。/ 2021年11月14日 13:08/ 0 赞/ 345 阅读