-
Notifications
You must be signed in to change notification settings - Fork 1
/
MaxAreaOfIsland.java
73 lines (69 loc) · 2.74 KB
/
MaxAreaOfIsland.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package com.hncboy;
/**
* @author hncboy
* @date 2019/11/29 10:01
* 695.岛屿的最大面积
*
* 给你一个大小为 m x n 的二进制矩阵 grid 。
* 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
* 岛屿的面积是岛上值为 1 的单元格的数目。
* 计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。
*
* 示例 1:
* 输入: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
* 通过次数 155,620 提交次数 232,643
*/
public class MaxAreaOfIsland {
public static void main(String[] args) {
MaxAreaOfIsland m = new MaxAreaOfIsland();
int[][] grid1 = {{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}};
int[][] grid2 = {{1}};
int[][] grid3 = {{0}};
System.out.println(m.maxAreaOfIsland(grid1));
System.out.println(m.maxAreaOfIsland(grid2));
System.out.println(m.maxAreaOfIsland(grid3));
}
public int maxAreaOfIsland(int[][] grid) {
int result = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
result = Math.max(result, dfs(i, j, grid));
}
}
}
return result;
}
private int dfs(int i, int j, int[][] grid) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0;
int currentIslandArea = 1;
currentIslandArea += dfs(i + 1, j, grid);
currentIslandArea += dfs(i - 1, j, grid);
currentIslandArea += dfs(i, j + 1, grid);
currentIslandArea += dfs(i, j - 1, grid);
return currentIslandArea;
}
}