The largest area of the island

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.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]]
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.

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Ideas (over 99.80%)

At first sight, I was scared to move, because I am not familiar with DFS. Put a day, after the simple problem brush, or have to face. It’s not that scary, recursive backtracking, going through a node and then empting it and counting.

Code implementation

int checkIsland(vector<vector<int>>& grid, int x, int y) {
        int count = 0;
        if (grid[x][y] == 0)
            return count;
        else {
            grid[x][y] = 0;
            count++;
            / /
            if (x - 1> =0)
                count += checkIsland(grid, x - 1, y);
            / / right
            if ((y + 1) < grid[0].size())
                count += checkIsland(grid, x, y + 1);
            / /
            if ((x + 1) < grid.size())
                count += checkIsland(grid, x + 1, y);
            / / left
            if ((y - 1) > =0)
                count += checkIsland(grid, x, y - 1);
        }
        return count;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.size() = =0)
            return 0;
        int max = 0;
        for (int i = 0; i < grid.size(a); i++) {for (int j = 0; j < grid[0].size(a); j++) {int temp = checkIsland(grid, i, j);
                if(temp > max) { max = temp; }}}return max;
    }
Copy the code

The largest area of the island