# 岛屿最大面积

## 使用案列

```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
```

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

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

### 深度优先搜索

#### 岛屿最大面积算法

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

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

#### 实施

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

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

#### 实施

##### 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
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
int area = 1;

/* create a queue to be used in BFS*/
/* push the current cell */

/* 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++;
}
}
}
/* 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）。 由于我们没有使用另一个矩阵空间来跟踪特定单元格是否已被访问，因此我们只需修改网格值，以便将已访问单元格标记为已访问。