Package g2001_2100.s2088_count_fertile_pyramids_in_a_land

Class Solution

java.lang.Object
g2001_2100.s2088_count_fertile_pyramids_in_a_land.Solution
public class Solution extends Object
2088 - Count Fertile Pyramids in a Land.<p>Hard</p> <p>A farmer has a <strong>rectangular grid</strong> of land with <code>m</code> rows and <code>n</code> columns that can be divided into unit cells. Each cell is either <strong>fertile</strong> (represented by a <code>1</code>) or <strong>barren</strong> (represented by a <code>0</code>). All cells outside the grid are considered barren.</p> <p>A <strong>pyramidal plot</strong> of land can be defined as a set of cells with the following criteria:</p> <ol> <li>The number of cells in the set has to be <strong>greater than</strong> <code>1</code> and all cells must be <strong>fertile</strong>.</li> <li>The <strong>apex</strong> of a pyramid is the <strong>topmost</strong> cell of the pyramid. The <strong>height</strong> of a pyramid is the number of rows it covers. Let <code>(r, c)</code> be the apex of the pyramid, and its height be <code>h</code>. Then, the plot comprises of cells <code>(i, j)</code> where <code>r <= i <= r + h - 1</code> <strong>and</strong> <code>c - (i - r) <= j <= c + (i - r)</code>.</li> </ol> <p>An <strong>inverse pyramidal plot</strong> of land can be defined as a set of cells with similar criteria:</p> <ol> <li>The number of cells in the set has to be <strong>greater than</strong> <code>1</code> and all cells must be <strong>fertile</strong>.</li> <li>The <strong>apex</strong> of an inverse pyramid is the <strong>bottommost</strong> cell of the inverse pyramid. The <strong>height</strong> of an inverse pyramid is the number of rows it covers. Let <code>(r, c)</code> be the apex of the pyramid, and its height be <code>h</code>. Then, the plot comprises of cells <code>(i, j)</code> where <code>r - h + 1 <= i <= r</code> <strong>and</strong> <code>c - (r - i) <= j <= c + (r - i)</code>.</li> </ol> <p>Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.</p> <p><img src="https://assets.leetcode.com/uploads/2021/11/08/image.png" alt="" /></p> <p>Given a <strong>0-indexed</strong> <code>m x n</code> binary matrix <code>grid</code> representing the farmland, return <em>the <strong>total number</strong> of pyramidal and inverse pyramidal plots that can be found in</em> <code>grid</code>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/12/22/1.JPG" alt="" /></p> <p><strong>Input:</strong> grid = [[0,1,1,0],[1,1,1,1]]</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> The 2 possible pyramidal plots are shown in blue and red respectively.</p> <p>There are no inverse pyramidal plots in this grid.</p> <p>Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/12/22/2.JPG" alt="" /></p> <p><strong>Input:</strong> grid = [[1,1,1],[1,1,1]]</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red.</p> <p>Hence the total number of plots is 1 + 1 = 2.</p> <p><strong>Example 3:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/12/22/3.JPG" alt="" /></p> <p><strong>Input:</strong> grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]</p> <p><strong>Output:</strong> 13</p> <p><strong>Explanation:</strong> There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.</p> <p>There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.</p> <p>The total number of plots is 7 + 6 = 13.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>m == grid.length</code></li> <li><code>n == grid[i].length</code></li> <li><code>1 <= m, n <= 1000</code></li> <li><code>1 <= m * n <= 10<sup>5</sup></code></li> <li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • countPyramids

      public int countPyramids(int[][] grid)