LeetCode 695.岛屿的最大面积

题目

给定一个包含了一些 0 和 1 的非空二维数组grid 。

一个岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个1必须在水平或者竖直方向上相邻。你可以假设grid的四个边缘都被0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例

[[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。

题目分析

此题与岛屿数量几乎一样。同样的，此题也采用深度优先搜索解决。

首先是深度优先搜索的过程，我们每搜索到一个岛屿，将其值置为0（避免重复搜索），令计数器+1。然后搜索其上下左右（注意边界）是否是岛屿（值是否为1）。

搜索岛屿的代码如下：

int dfs(int** grid, int raw, int col, int r, int c, int num){
    grid[r][c] = 0;
    num++;
    if (r - 1 >= 0  && grid[r-1][c] == 1) num = dfs(grid, raw, col, r - 1, c, num);
    if (r + 1 < raw && grid[r+1][c] == 1) num = dfs(grid, raw, col, r + 1, c, num);
    if (c - 1 >= 0  && grid[r][c-1] == 1) num = dfs(grid, raw, col, r, c - 1, num);
    if (c + 1 < col && grid[r][c+1] == 1) num = dfs(grid, raw, col, r, c + 1, num);
    return num;
}

搜索的代码完成，此题也就基本完成了。然后按照二元数组的遍历过程，依次遍历每个元素，遇到岛屿就进入dfs即可。

int raw = gridSize;
int col = gridColSize[0];
int res = 0;
for (int i = 0; i < raw; i++){
    for (int j = 0; j < col; j++){
        if (grid[i][j] == 1){
            int temp = dfs(grid, raw, col, i, j, 0);
            if (temp > res) res = temp;
        }
    }
}

最后返回res即可。

题目解答

深度优先搜索

int dfs(int** grid, int raw, int col, int r, int c, int num){
    grid[r][c] = 0;
    num++;
    if (r - 1 >= 0  && grid[r-1][c] == 1) num = dfs(grid, raw, col, r - 1, c, num);
    if (r + 1 < raw && grid[r+1][c] == 1) num = dfs(grid, raw, col, r + 1, c, num);
    if (c - 1 >= 0  && grid[r][c-1] == 1) num = dfs(grid, raw, col, r, c - 1, num);
    if (c + 1 < col && grid[r][c+1] == 1) num = dfs(grid, raw, col, r, c + 1, num);
    return num;
}
int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
    int raw = gridSize;
    int col = gridColSize[0];
    int res = 0;
    for (int i = 0; i < raw; i++){
        for (int j = 0; j < col; j++){
            if (grid[i][j] == 1){
                int temp = dfs(grid, raw, col, i, j, 0);
                if (temp > res) res = temp;
            }
        }
    }
    return res;
}