岛屿最大面积


难度级别 中等
经常问 亚马逊 彭博 DoorDash Facebook 谷歌 神谕 Palantir Technologies
排列 广度优先搜索 深度优先搜索 图表 矩阵

问题描述:给定2D矩阵,该矩阵只有0(代表水)和1(代表土地)作为条目。 矩阵中的一个孤岛是通过将所有相邻的1的4方向(水平和垂直)连接起来而形成的。 在中找到岛屿的最大面积 矩阵。 假设网格的所有四个边缘都被水包围。

备注:孤岛组的面积是该孤岛组中的像元数。

使用案列

Input 1: 
Grid = {{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,1,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,1,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}}

Output: Area of largest island = 12 


Input 2: 
Grid = {{0,1,0,0,1,1,0}, 
        {0,0,0,0,1,0,0}, 
        {0,0,0,1,1,0,0}, 
        {0,0,1,1,0,0,0}}

Output: Area of largest island = 7

考虑上面给出的第一个输入示例。 下面是上述2D网格的表示,代表陆地的单元标记为1(绿色),代表水的单元标记为0(蓝色)。

岛屿最大面积

从该图可以看出,形成了5个岛组。 最大的岛屿组以红色勾勒出轮廓,而较小的岛屿组以黄色勾勒出轮廓。 最大的岛屿群面积为12个单位。

岛屿最大面积

请注意: 应当注意,通过在水平方向(左右)和垂直方向(上和下)(而不是对角线方向)上连接网格单元来形成岛组。

岛屿最大面积的解决方案类型

  1. 深度优先搜索
  2. 广度优先搜索

深度优先搜索

岛屿最大面积的进近

我们旨在通过递归访问包含1的单元的所有邻居(以及这些邻居的邻居)来计算最大岛屿的面积。通过执行以下操作来实现对邻居和邻居的邻居的递归遍历 DFS。 在执行DFS时,对于每个新访问的单元(仅包含1个),我们递归地将访问的总面积增加1。

岛屿最大面积算法

  1. 遍历2D网格,并从包含1的每个像元执行DFS遍历。
  2. 通过将单元格值更改为0,将当前单元格标记为已访问。
  3. 从当前单元格开始的岛屿面积为1。
  4. 递归访问当前包含1的单元格的所有邻居(从右上-左下),将这些邻居标记为已访问,并为每个访问的有效邻居(值为1的单元)将区域增加1(通过更改单元格的值)到0)。
  5. 遍历完成后,返回获得的面积。
  6. 对每个包含2,3,4的(矩阵)单元格执行步骤5、1、XNUMX和XNUMX,并返回获得的所有面积值的最大值。

考虑上面给出的示例网格:我们从具有值1的最大岛的最左侧和最顶部的单元格开始(到此,此单元格上方和左侧的所有单元格都已被访问过)并执行DFS遍历。

DFS遍历会访问特定方向上可能达到最大深度的单元。 从特定单元格开始的遍历方向按以下顺序:上-右-下-左。 DFS遍历 算法 从最大岛屿的最顶部和最左侧的单元开始,如下图所示:

在最大的岛屿上拜访过的牢房已标记为rad。

岛屿最大面积

岛屿最大面积

岛屿最大面积

岛屿最大面积

岛屿最大面积

正如我们所观察到的,遍历过程中遍历的细胞数为12。因此,最大岛的面积为12。

实施

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to perform DFS in four directions(up-right-down-left)
int dfs(vector<vector<int>>& grid, int row, int col) 
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* since the current cell has value = 1
        minimum area we start with is 1*/
    int area = 1;
    
    /* since you have already visited the current cell
    mark it as already visited */
    grid[row][col] = 0;
    
    /* used for traversing in four directions(up-right-down-left)*/
    vector<int> dir({-1,0,1,0,-1});
    
    /* we begin our traversal into four directions from the current cell*/
    for (int i = 0; i < 4; i++) 
    {
        int r = row+dir[i], c = col+dir[i+1];
        
        /* make traversals only when next cell lies within the matrix and is unvisited*/
        if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
            area += dfs(grid, r, c);
    }
    /* total number of cells with value 1 visited from the current cell */
    return area;
}

/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* stores the area of largest consecutive 1's*/
    int maxArea = 0;
    
    /* visit each cell of the matrix*/
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
        /* begin your traversal from the cell which has value as 1(land)*/
            if (grid[i][j] == 1) 
            /* store the largest area*/
            maxArea = max(maxArea, dfs(grid, i, j));
            
    return maxArea;    
}

/* main function to implement above function */
int main()
{
    vector<vector<int>> grid = {{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,1,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,1,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}};
    
    
    cout<<"Area of largest island = "<<largestIsland(grid);
    
    return 0;
}
Area of largest island = 12
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    // function to perform DFS in four directions(up-right-down-left)
    static int dfs(int grid[][], int row, int col) 
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* since the current cell has value = 1
            minimum area we start with is 1*/
        int area = 1;
        
        /* since you have already visited the current cell
        mark it as already visited */
        grid[row][col] = 0;
        
        /* used for traversing in four directions(up-right-down-left)*/
        int [] dir = {-1,0,1,0,-1};
        
        /* we begin our traversal into four directions from the current cell*/
        for (int i = 0; i < 4; i++) 
        {
            int r = row+dir[i], c = col+dir[i+1];
            
            /* make traversals only when next cell lies within the matrix and is unvisited*/
            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
                area += dfs(grid, r, c);
        }
        /* total number of cells with value 1 visited from the current cell */
        return area;
    }

    
    /* function that returns area of largest island */
    static int largestIsland(int grid[][])
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* stores the area of largest consecutive 1's*/
        int maxArea = 0;
        
        /* visit each cell of the matrix*/
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
            /* begin your traversal from the cell which has value as 1(land)*/
                if (grid[i][j] == 1) 
                /* store the largest area*/
                maxArea = Math.max(maxArea, dfs(grid, i, j));
                
        return maxArea;    
    }
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        int grid[][] =  {{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,1,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,1,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}};
    
        System.out.print("Area of largest island = "+largestIsland(grid)); 
    }
}
Area of largest island = 12

岛屿最大面积的复杂度分析

  1. 时间复杂度:T(n)= O(R * C),我们恰好遍历矩阵的每个单元一次。
  2. 空间复杂度:A(n)= O(R * C),因为我们没有使用另一个矩阵空间来跟踪是否已访问过某个特定的单元格,所以我们只需修改网格值,以便标记已访问的单元格如访问。

广度优先搜索

岛屿最大面积的进近

我们的目的是通过迭代访问包含1的单元的所有邻居(以及这些邻居的邻居)来计算最大岛屿的面积。通过执行BFS,可以实现遍历邻居和邻居的迭代遍历。 在执行BFS时,对于每个新访问的单元(仅包含1个),我们将访问的总面积迭代增加1。

岛屿最大面积算法

  1. 遍历2D网格,并从包含1的每个像元执行BFS遍历。
  2. 通过将单元格值更改为0,将当前单元格标记为已访问。
  3. 从当前单元格开始的岛屿面积为1。
  4. 迭代访问包含1的当前单元格的所有邻居(从右上-左下),将这些邻居标记为已访问,并为每个访问的有效邻居(值为1的单元格)将区域增加1(通过更改单元格值到0)。
  5. 遍历完成后,返回获得的面积。
  6. 对每个包含2,3,4的(矩阵)单元格执行步骤5、1、XNUMX和XNUMX,并返回获得的所有面积值的最大值。

考虑上面给出的示例网格:我们从具有值1的最大岛屿的最左侧和最顶部的单元格开始(到此,此单元格上方和左侧的所有单元格都已被访问)并执行BFS遍历。

BFS遍历首先访问特定小区的所有邻居小区(从右上-左下),然后迭代访问这些邻居的邻居。 下面显示了最大岛的最顶部和最左侧单元的BFS遍历算法:

在最大的岛屿上访问过的牢房已标记为红色。

正如我们所观察到的,遍历过程中遍历的细胞数为12。因此,最大岛的面积为12。

实施

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to perform BFS in four directions(up-right-down-left)
int bfs(vector<vector<int>>& grid, int row, int col) 
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* since the current cell has value = 1
            minimum area we start with is 1*/
    int area = 1;
    
    /* create a queue to be used in BFS*/
    queue<pair<int,int>> q;
    /* push the current cell */
    q.push({row, col});
    
    /* since you have already visited the current cell
        mark it as already visited */
    grid[row][col] = 0;
    /* used for traversing in four directions(up-right-down-left)*/
    vector<int> dir({-1,0,1,0,-1});
    
    /* begin BFS traversal */
    while (!q.empty()) 
    {
        /* pop a cell with containing 1(land) */
        int y = q.front().first, x = q.front().second;
        q.pop();
        
        /* we begin our traversal into four directions from the current cell*/
        for (int i = 0; i < 4; i++) 
        {
            int r = y+dir[i], c = x+dir[i+1];
            /* make traversals only when next cell lies within the matrix and is unvisited*/
            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
            {
                /* mark next cell as visited, increase the visited area and push next cells into the queue*/
                grid[r][c] = 0;
                area++;
                q.push({r,c});
            }
        }
    }
    /* total number of cells with value 1 visited from the current cell */
    return area;
}
/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* stores the area of largest consecutive 1's*/
    int maxArea = 0;
    
    /* visit each cell of the matrix*/
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
        /* begin your traversal from the cell which has value as 1(land)*/
            if (grid[i][j] == 1) 
            /* store the largest area*/
            maxArea = max(maxArea, bfs(grid, i, j));
            
    return maxArea;    
}

/* main function to implement above function */
int main()
{
    vector<vector<int>> grid = {{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,1,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,1,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}};
    
    
    cout<<"Area of largest island = "<<largestIsland(grid);   
    return 0;
}
Area of largest island = 12
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    /* define pair class to handle 2D co-ordinates in a matrix*/
    static class pair
    {
        int row;
        int col;
        
        pair(int y,int x)
        {
            row = y;
            col = x;
        }
    }
    // function to perform DFS in four directions(up-right-down-left)
    static int dfs(int grid[][], int row, int col) 
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* since the current cell has value = 1
                minimum area we start with is 1*/
        int area = 1;
        
        /* create a queue to be used in BFS*/
        Queue<pair> q = new LinkedList<pair>();
        /* push the current cell */
        q.add(new pair(row, col));
        
        /* since you have already visited the current cell
            mark it as already visited */
        grid[row][col] = 0;
        /* used for traversing in four directions(up-right-down-left)*/
        int [] dir = {-1,0,1,0,-1};
        
        /* begin BFS traversal */
        while (!q.isEmpty()) 
        {
            /* pop a cell with containing 1(land) */
            pair p = q.remove();
            int y = p.row, x = p.col;
            
            /* we begin our traversal into four directions from the current cell*/
            for (int i = 0; i < 4; i++) 
            {
                int r = y+dir[i], c = x+dir[i+1];
                /* make traversals only when next cell lies within the matrix and is unvisited*/
                if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
                {
                    /* mark next cell as visited, increase the visited area and push next cells into the queue*/
                    grid[r][c] = 0;
                    area++;
                    q.add(new pair(r,c));
                }
            }
        }
        /* total number of cells with value 1 visited from the current cell */
        return area;
    }

    
    /* function that returns area of largest island */
    static int largestIsland(int grid[][])
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* stores the area of largest consecutive 1's*/
        int maxArea = 0;
        
        /* visit each cell of the matrix*/
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
            /* begin your traversal from the cell which has value as 1(land)*/
                if (grid[i][j] == 1) 
                /* store the largest area*/
                maxArea = Math.max(maxArea, dfs(grid, i, j));
                
        return maxArea;    
    }
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        int grid[][] =  {{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,1,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,1,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}};
    
        System.out.print("Area of largest island = "+largestIsland(grid)); 
    }
}
Area of largest island = 12

岛屿最大面积的复杂度分析

  1. 时间复杂度:T(n)= O(R * C),我们恰好遍历矩阵的每个单元一次。
  2. 空间复杂度:A(n)= O(R * C)。 由于我们没有使用另一个矩阵空间来跟踪特定单元格是否已被访问,因此我们只需修改网格值,以便将已访问单元格标记为已访问。

參考資料