[depth first search] 695 Maximum area of the island

One 、 subject

Give you a size of m x n The binary matrix of grid .

Islands It's made up of some neighboring 1 ( Representing land ) A combination of components , there 「 adjacent 」 Ask for two 1 Must be in In four horizontal or vertical directions adjacent . You can assume grid The four edges of are all 0（ Representative water ） Surrounded by a .

The area of the island is the value of 1 Number of cells .

Calculate and return grid The largest island area in . If there were no Islands , Then the return area is 0 .

Example 1：

Input ：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,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]]
Output ：6
explain ： The answer should not be 11 , Because the island can only contain horizontal or vertical 1 .
Example 2：

Input ：grid = [[0,0,0,0,0,0,0,0]]
Output ：0

Two 、 Answer key

This question is a typical search question , An island here is also equivalent to a ring , So we use depth first search .
The implementation of depth first search generally requires a main function and an auxiliary function , The main function is used to traverse all positions , Judge and serve as the starting point of the search ; Auxiliary functions are used for a depth first search . among , Depth first search can be realized by recursion or stack , Recursive implementation is relatively easy , It can be used to brush questions , There are many projects in the stack , It can prevent the recursive stack from being full .
in addition , Once recursion is used, we should consider the boundary conditions and what operations should be carried out under the boundary conditions . There are two ways to deal with recursive boundaries ：

• Judge the boundary first , Re recursion
• Recursion first , Judge the boundary again
  These two methods correspond to two ways of writing auxiliary functions , as follows .

Be careful ： When using recursive operation, the searched position here is to prevent it from being searched again , The corresponding location should be marked as visited .

3、 ... and 、 Code

• Judge the boundary first , Re recursion

class Solution {
    
public:
    vector<int> direction{
    -1,0,1,0,-1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
     if(grid.empty()||grid[0].empty()) return 0;
     int res = 0;
     for(int i = 0;i<grid.size();i++){
    
         for(int j = 0;j<grid[0].size();j++){
    
             if(grid[i][j]== 1){
    
                res = max(res,dfs(grid,i,j));
             }

         }
     }
     return res;
    }

    int dfs(vector<vector<int>>& grid,int i,int j){
    
        if(grid[i][j]==0) return 0;
        grid[i][j] = 0;
        int r,c,count = 1;
        for(int k=0;k<4;k++){
    
           r = i +  direction[k];
           c =  j+direction[k+1];
           if(r < grid.size() && c < grid[0].size() && r >=0 && c>=0 && grid[r][c]!=0){
    
               count += dfs(grid,r,c);
           }
        }
        return count;
    }

};

• Recursion first , Judge the boundary again

class Solution {
    
public:
    vector<int> direction{
    -1,0,1,0,-1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
     if(grid.empty()||grid[0].empty()) return 0;
     int res = 0;
     for(int i = 0;i<grid.size();i++){
    
         for(int j = 0;j<grid[0].size();j++){
    
                res = max(res,dfs(grid,i,j));
         }
     }
     return res;
    }

    int dfs(vector<vector<int>>& grid,int i,int j){
    
        if(i < grid.size() && j < grid[0].size() && i >=0 && j>=0 && grid[i][j]!=0){
    
            grid[i][j] = 0;
            return 1+dfs(grid,i-1,j)+dfs(grid,i,j-1)+dfs(grid,i+1,j)+dfs(grid,i,j+1);
        }
        else return 0;
        
    }

};