給定一個包含了一些 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。
此方法過程如下:
對于這種重複的操作,顯然離不開循環或遞歸。在此便采用遞歸的方式解決。
class Solution {
public static int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
int area = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
//以此為中心,向四周擴散
area = GetArea(grid, i, j);
maxArea = maxArea > area ? maxArea : area;
}
}
}
return maxArea;
}
public static int GetArea(int[][] grid, int i, int j) {
//由于坐标每次變化 1 個機關,是以判斷是否等于數組長度即可
if (i == grid.length || i < 0)
return 0;
else if (j == grid[0].length || j < 0)
return 0;
if (grid[i][j] == 1) {
grid[i][j] = 0;
return 1 + GetArea(grid, i + 1, j) + GetArea(grid, i - 1, j) + GetArea(grid, i, j + 1) + GetArea(grid, i, j - 1);
}
return 0;
}
}
複制
注意:為了確定每個土地通路不超過一次,我們每次經過一塊土地時,将這塊土地的值置為 0。這樣我們就不會多次通路同一土地。