【每日打卡】[leetcode]695-岛屿的最大面积

编程我只用CPP

2020 年 03 月 15 日

24 次浏览

暂无评论

3070字数

数据结构和算法

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/max-area-of-island

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为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。

二、题解

和地图相关的题目求最值，第一个想到的都应该是深度优先搜索，例如求两点间的最短路径、迷宫找最短出口等，都可以用深搜来解决问题。当然，出了深搜以外，还可以通过回溯来解决。深搜实际上是递归，而回溯则是迭代。

使用深搜的思路：遍历每个地图点，如果是陆地，就往四个方向上继续蔓延，一旦遍历到非陆地或者超出地图范围了就返回。

要注意的问题是，当一个点蔓延到另外一个点后，另外一个点也可能会蔓延回来。例如A是B的左节点，B作为陆地蔓延到A后又会作为A的右节点蔓延回来。这种情况下就导致重复计算，所以为了避免重复处理，需要特殊处理这个问题。可以采取的办法是每访问到一个节点，就把它变成海洋。

输入数据需要考虑的特殊场景：空地图，地图只有一列或一行。

三、代码

class Solution {
    /*
     * @grid 地图
     * @i/j 需要计算的地图坐标
     * @row/col 地图的行数和列数
     * @return 返回相连的面积
     */
    int dfs(vector<vector<int>> &grid, int i, int j, const int row, const int col) {
        int top, bottom, left, right;
        // dfs退出条件，到达了边界，或者当前值为0
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0)
            return 0;

        // 已经访问过的节点置为0，避免重复计算
        grid[i][j] = 0;

        // 分别计算上下左右四个方向上的面积
        top = dfs(grid, i + 1, j, row, col);
        bottom = dfs(grid, i - 1, j, row, col);
        right = dfs(grid, i, j + 1, row, col);
        left = dfs(grid, i, j - 1, row, col);

        // 返回总面积
        return top + bottom + left + right + 1;
    }

public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int i, j, row, col, res;

        if (grid.empty())
            return 0;

        row = grid.size();
        col = grid[0].size();

        res = 0;
        for (i = 0; i < row; i++) {
            for (j = 0; j < col; j++) {
                // 提前剪枝
                if (grid[i][j] == 0)
                    continue;

                // 遍历每一个节点
                res = max(res, dfs(grid, i, j, row, col));
            }
        }
        return res;
    }
};

测试案例：

TEST(leetcode, demo) {
    Solution s;
    vector<vector<int>> input1{
            {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}
    }, input2{{1}}, input3{{0,0,0,0,0,0}}, input4;

    EXPECT_EQ(s.maxAreaOfIsland(input1), 6);
    EXPECT_EQ(s.maxAreaOfIsland(input2), 1);
    EXPECT_EQ(s.maxAreaOfIsland(input3), 0);
    EXPECT_EQ(s.maxAreaOfIsland(input4), 0);
}