Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
思路：
- 我們可以遍歷每個(gè)島务甥，找出那個(gè)最大面積的島筛峭。
- 遍歷2維數(shù)組中每一個(gè)元素韩肝，如果它是1，則沿著它繼續(xù)向周?chē)阉靼缡冢业剿信彽年懙兀@樣最終可以得到它所在的那個(gè)島的面積专肪。
- 每遍歷到一個(gè)陸地刹勃，需要把它標(biāo)記為0，否則搜索它毗鄰陸地的時(shí)候嚎尤，會(huì)重復(fù)的搜索回來(lái)荔仁。
- 用一個(gè)最大值變量來(lái)存儲(chǔ)當(dāng)前遍歷到的最大面積。
public class MaxAreaIsland695 {
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid[0].length == 0 || grid[0].length == 0) {
return 0;
}
int maxArea = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, searchArea(grid, i, j));
}
}
}
return maxArea;
}
private int searchArea(int[][] grid, int x, int y) {
grid[x][y] = 0;
int curArea = 1;
for (int d = 0; d < 4; d++) {
int tx = x + dx[d];
int ty = y + dy[d];
if (tx < 0 || tx >= grid.length || ty < 0 || ty >= grid[0].length || grid[tx][ty] == 0) {
continue;
}
curArea += searchArea(grid, tx, ty);
}
return curArea;
}
}
