This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

1, the title

Given a grid, a non-empty two-dimensional array containing some zeros and ones.

An island is a combination of adjacent ones (land) that must be either horizontal or vertical. You can assume that all four edges of the grid are surrounded by zeros (for water).

Find the largest island area in the given two-dimensional array. (If there are no islands, the return area is 0.)

Example 1:

,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,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]. ,1,0,0,1,1,0,0,1,1,1,0,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]]Copy the code

I should return 6 for the given matrix above. Note that the answer should not be 11, as islands can only contain 1’s in four directions, horizontal or vertical.

Example 2:

[[0,0,0,0,0,0,0,0]]
Copy the code

For the given matrix above, return 0.

Note: The given matrix grid is not more than 50 in length or width.

2, train of thought

∗ (DFS) O (n m) O (n * m) O n ∗ (m)

Given a grid consisting of 0 and 1, find the largest island area in the array. If there is none, return 0.

Sample:

As shown in the example, the two-dimensional array grid has a maximum island area of 4. Here’s how to do depth-first search.

We define a search sequence in which one piece of land on the island is searched, and then each piece of land connected to it is explored in four directions. During the search process, an area variable is maintained to record the total amount of land searched. In order to avoid repeated search, we need to set the searched land to 0 in this process, and finally return the largest area.

Search function design:

int dfs(int x, int y)
Copy the code

X, y are the horizontal and vertical coordinates of the currently searched two-dimensional array grid.

Implementation details:

  • 1. To ensure that each location is searched only once, you need to mark the current location to indicate that the location has been searched.
  • 2, the two-dimensional arraygridAnd the number of rows in a two-dimensional arraynAnd the number of columnsmGlobal variables are defined to reduce the search functiondfsThe number of arguments.
  • 3. Use offset arrays to simplify code, as shown below:

The specific process is as follows:

  • 1, define,res = 0To traverse thegridThe array.
  • 2. If the currentgridArray elementgrid[i][j] == 1That is to say, for the land, the current land(i,j)For the starting point continue to search the surrounding area.
  • 3. Record the total number of connected lands until all connected lands of the current land are searchedareaIn the.
  • 4, implementres = max(res,area)“, constantly updated answers.

Time complexity analysis: O(n∗m)O(n*m)O(n∗m) O(n*m)O(n∗m), where NNN is the number of rows in a two-dimensional array, MMM is the number of columns in a two-dimensional array, and each position is searched only once.

C++ code

class Solution {
public:
    int n, m;
    vector<vector<int>>g;
    int dx[4] = {- 1.0.1.0}, dy[4] = {0.1.0.- 1}; // Offset the array
    int dfs(int x, int y) // Search function
    {
        int area = 1;
        g[x][y] = 0;  // Already searched, marked 0
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            // The current land is not out of bounds and has not been searched, proceed to the next level of search
            if(a >=0 && a < n && b >=0 && b < m && g[a][b])
                area += dfs(a, b);
        }      
        return area; // Return the total number of connected lands
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        g = grid;
        int res = 0;
        n = grid.size(), m = grid[0].size();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(g[i][j])
                    res = max(res,dfs(i,j));
        returnres; }};Copy the code

4. Java code

class Solution {
    private int n, m;
    private int[][] g;
    private int[] dx = {-1.0.1.0}, dy = {0.1.0, -1};// Offset the array
    public int dfs(int x, int y) // Search function
    {
        int area = 1;
        g[x][y] = 0; // Already searched, marked 0
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            // The current land is not out of bounds and has not been searched, proceed to the next level of search
            if(a >=0 && a < n && b >= 0&& b < m && g[a][b] ! =0)
                area += dfs(a, b);
        }      
        return area; // Return the total number of connected lands
    }
    public int maxAreaOfIsland(int[][] grid) {
        g = grid;
        int res = 0;
        n = grid.length; m = grid[0].length;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(g[i][j] ! =0)
                    res = Math.max(res,dfs(i,j));
        returnres; }}Copy the code

Original link: 695. The largest area of the island