The number of enclaves

The number of enclaves

stay m*n The size of gird in , among 0 On behalf of the ocean ,1 Representing land , The title is to find the number of lands wrapped by the ocean , Finally, return the number of lands surrounded by the ocean .

Their thinking

First, the enclave problem is a simple matrix traversal problem , A little method is added to the basic matrix traversal , The enclave problem is solved .

First, we create a method ,DFS Method （ Depth first search method ）

void DFS(int** grid,int i,int j,int n,int* m){
    if(i<0||j<0||j=>m||i=>n) return;
    if(grid[i][j]==0) return;
    grid[i][j]=0;
    DFS(grid,i,j+1,n,m);
    DFS(grid,i,j-1,n,m);
    DFS(grid,i+1,j,n,m);
    DFS(grid,i-1,j,n,m);
}

The idea of recursion is also used here, which will be discussed in Chapter i+1 That's ok , The first j+1 Check the upper, lower, left and right nodes of the elements of the column , If it is land, change it into ocean , Because in C Language cannot be used grid.length,grid[0].length. So at the end of this function, we add the length and width of the whole matrix .（ If a boss finds out how to put the long broadband of the matrix into this method, he hopes to leave your footprints in the comment area , Xiaobai really needs your help ）

Second, let's first make sure that nothing at the boundary of the matrix counts , Then we will first eliminate the land around the boundary , The elimination method is to call the above method to find the land near the boundary , And change them into oceans ( For convenience, we use n,m)

for(int i=0;i<n;i++){
    DFS(grid,i,0,n,m);
    DFS(grid,i,m-1,n,m);
}
for(int j=0;j<m;j++){
    DFS(grid,0,j,n,m);
    DFS(grid,n-1,j,n,m);
}

Finally, we traverse the matrix directly 1 The node of , Count with one parameter .( You can check the number of islands in )

for(int i=0;i<n;i++)
    for(int j=0;j<m;j++){
        if(grid[i][j]==1) sum++;
}

for(int i=0;i<n;i++)            
    for(int j=0;j<m;j++){
        if(grid[i][j]==1){
            sum++;
            DFS(grid,i,j,n,m);        // Add this if you want to query the number of islands 
        }
}

Add the return value at the end to complete .（ Here's the complete code ）

Complete code

void Dfs(int** grid,int i,int j,int n,int* m){
    if(i<0||j<0||i>=n||j>=*m) return;
    if(grid[i][j]==0) return;
    grid[i][j]=0;
    Dfs(grid,i,j+1,n,m);
    Dfs(grid,i,j-1,n,m);
    Dfs(grid,i+1,j,n,m);
    Dfs(grid,i-1,j,n,m);
}
int numEnclaves(int** grid, int n, int* m){
    int sum=0;
    for(int i=0;i<n;i++){
        Dfs(grid,i,0,n,m);
        Dfs(grid,i,*m-1,n,m);
    }
    for(int j=0;j<*m;j++){
        Dfs(grid,0,j,n,m);
        Dfs(grid,n-1,j,n,m);    
    }
    for(int i=0;i<=m-1;i++)
        for(int j=0;j<*m;j++){
            if(grid[i][j]==1){
                sum++;
            }
        }
    return sum;
}