#2088
Count Fertile Pyramids in a Land
expert · 1060 · lc hard +32 · verified · 66.3% accepted · 396 likes · top 71%
Description
Given a 0-indexed m x n binary matrix grid (1 = fertile, 0 = barren), count all pyramidal and inverse pyramidal plots. A pyramid of height h >= 2 has its apex at (r, c) and widens by one cell on each side per row going down, spanning rows r to r + h - 1. An inverse pyramid has its apex at the bottom and widens going up. Every cell in the plot must be fertile. Return the combined count of both pyramid types.
Example 1:
Input: grid = [[0,1,1,0],[1,1,1,1]]
Output: 2
Explanation: The 2 possible pyramidal plots are shown in blue and red respectively.
There are no inverse pyramidal plots in this grid.
Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.
Example 2:
Input: grid = [[1,1,1],[1,1,1]]
Output: 2
Explanation: The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red.
Hence the total number of plots is 1 + 1 = 2.
Example 3:
Input: grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
Output: 13
Explanation: There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.
There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.
The total number of plots is 7 + 6 = 13.
Code
1
2
3