695. Max Area of Island
- 1 minutes read - 421 wordsLeetcode 695. Max Area of Island
題目
You are given an m x n binary matrix grid.
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.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
想法
這是個找地圖中最大陸塊大小的問題。
想法是在遍歷整張地圖時,如果遇到的是陸地,則用 DFS 找該陸地所屬陸塊的大小。
然後輸出其中最大值。
實作
Javascript
var maxAreaOfIsland = function (grid) {
// m 是長度, n 是寬度
const m = grid.length,
n = grid[0].length;
// 找陸地的方法
function find(x, y) {
// 如果是 (x, y) 是海洋或是已經找過了,就不要繼續
if (grid[y][x] == 0 || grid[y][x] == 2) return 0;
// area 是這一個陸塊的大小
let area = 1;
// 紀錄這塊地已找過
grid[y][x] = 2;
// 如果右邊不是邊界,找右邊
if (x + 1 < n) area += find(x + 1, y);
// 如果左邊不是邊界,找左邊
if (x > 0) area += find(x - 1, y);
// 如果下面不是邊界,找下面
if (y + 1 < m) area += find(x, y + 1);
// 如果上面不是邊界,找上面
if (y > 0) area += find(x, y - 1);
// 回傳該陸塊總大小
return area;
}
let max = 0;
// 遍歷所有位置
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// 如果是陸地,則找該陸地所屬陸塊大小
if (grid[i][j] == 1) {
let area = find(j, i);
max = area > max ? area : max;
}
}
}
return max;
};