[daily problem insight] prefix and -- count the number of fertile pyramids in the farm

️ Winter vacation xinkeng —— Code Fox's daily notes
The winter vacation is about to expire

2088. Count the number of fertile pyramids in the farm -Hard( Prefix and quick detection array )- The first 66 Biweekly competition question 4

There is one Rectangular grid A shapeless farm , Divided into m That's ok n Cell of column . Each grid is either Fertile （ use 1 Express ）, Or poor Of （ use 0 Express ）. All and grids outside the grid are considered barren .

On the farm The pyramid The area is defined as follows ：

1. Number of grids in the area Greater than 1 And all the grids are Fertile .
2. The pyramid Apex It's this pyramid The top Lattice of . The height of the pyramid is the number of rows it covers . Make (r, c) It is the top of the pyramid and its height is h , Then any grid contained in the pyramid area (i, j) Need to meet r <= i <= r + h - 1 And c - (i - r) <= j <= c + (i - r) .

One Inverted Pyramid Similar definitions are as follows ：

1. Number of grids in the area Greater than 1 And all the grids are Fertile .
2. Inverted pyramid Apex It's the inverted pyramid At the bottom Lattice of . The height of the inverted pyramid is the number of rows it covers . Make (r, c) It is the top of the pyramid and its height is h , Then any grid contained in the pyramid area (i, j) Need to meet r - h + 1 <= i <= r And c - (r - i) <= j <= c + (r - i) .

class Solution {
    
    public int countPyramids(int[][] grid) {
    
        int m=grid.length;
        int n=grid[0].length;
        for(int i=0;i<m;i++){
    
            for(int k=0;k<n;k++){
    
                if(k!=0){
    
                    grid[i][k]+=grid[i][k-1];
                }
            }
        }
        
        int ans=0;
        for(int x=0;x<m;x++){
    
            for(int y=0;y<n;y++){
    
                int h=1;
                
                if(y==0&&grid[x][y]==0){
    
                    continue;
                }
                if(y!=0&&grid[x][y]-grid[x][y-1]==0){
    
                    continue;
                }
                
                while(x+h<m&&y+h<n&&y-h>=0){
    
                    int sum=0;
                    if(y-h==0){
    
                        sum=grid[x+h][y+h];
                    }
                    else{
    
                        sum=grid[x+h][y+h]-grid[x+h][y-h-1];
                    }
                    
                    if(sum==2*h+1){
    
                        ans++;
                        h++;
                    }
                    else{
    
                        break;
                    }
                }
                h=1;
                while(x-h>=0&&y+h<n&&y-h>=0){
    
                    int sum=0;
                    if(y-h==0){
    
                        sum=grid[x-h][y+h];
                    }
                    else{
    
                        sum=grid[x-h][y+h]-grid[x-h][y-h-1];
                    }
                    
                    if(sum==2*h+1){
    
                        ans++;
                        h++;
                    }
                    else{
    
                        break;
                    }
                }
            }
        }
        return ans;
    }
}

ending

Title source ： Power button （LeetCode） link ：https://leetcode-cn.com/problems

️ Focus on the author , Take you to brush the questions , Learn the most commonly used algorithm skills from simple algorithm problems （ Winter vacation every day ）
️ Pay attention to the author's questions —— Simple to advanced , Let you unknowingly become a ruthless problem brushing machine , If you have any questions, please send a private letter