695. Max Area of Island

- 1 minutes read - 421 words

Leetcode 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;
};