695. Max Area of Island 岛屿的最大面积

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.)

Example 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]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50

给定一个非空的二维阵列网格为0和1，一个岛是一组1（代表陆地）四方向（水平或垂直）。您可以假设网格的所有四个边缘被水包围。在给定的2D数组中找到一个岛的最大面积。（如果没有岛，最大面积为0.）

解法：用广度优先法遍历值为1的坐标，用set保存已遍历过的坐标

var maxAreaOfIsland = function (grid) {
    let max = 0;
    let posSet = new Set();
    for (let r = 0; r < grid.length; r++) {
        let row = grid[r];
        for (let c = 0; c < row.length; c++) {
            if (row[c] === 0 || posSet.has(getPosStr(r, c))) continue;
            let block = 0;
            let queue = [{ r, c }];
            posSet.add(getPosStr(r, c));
            while (queue.length > 0) {
                block++;
                let pos = queue.shift();
                let posRow = pos.r;
                let posCol = pos.c;
                if (posRow >= 1 && grid[posRow - 1][posCol] == 1 && !posSet.has(getPosStr(posRow - 1, posCol))) {
                    queue.push({ r: posRow - 1, c: posCol });
                    posSet.add(getPosStr(posRow - 1, posCol));
                }
                if (posRow < grid.length - 1 && grid[posRow + 1][posCol] == 1 && !posSet.has(getPosStr(posRow + 1, posCol))) {
                    queue.push({ r: posRow + 1, c: posCol });
                    posSet.add(getPosStr(posRow + 1, posCol));
                }
                if (posCol >= 1 && grid[posRow][posCol - 1] == 1 && !posSet.has(getPosStr(posRow, posCol - 1))) {
                    queue.push({ r: posRow, c: posCol - 1 });
                    posSet.add(getPosStr(posRow, posCol - 1));
                }
                if (posCol < row.length - 1 && grid[posRow][posCol + 1] == 1 && !posSet.has(getPosStr(posRow, posCol + 1))) {
                    queue.push({ r: posRow, c: posCol + 1 });
                    posSet.add(getPosStr(posRow, posCol + 1));
                }
            }
            max = Math.max(max, block);
        }
    }
    return max;
};
let getPosStr = (x, y) => {
    return x + "," + y;
}

来自为知笔记(Wiz)

原文链接: https://www.cnblogs.com/xiejunzhao/p/7638781.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/261007

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

695. Max Area of Island 岛屿的最大面积

相关推荐