count-fertile-pyramids-in-a-land

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A farmer has a rectangular grid of land with <code>m</code> rows and <code>n</code> columns that can be divided into unit cells. Each cell is either fertile (represented by a <code>1</code>) or barren (represented by a <code>0</code>). All cells outside the grid are considered barren.

A pyramidal plot of land can be defined as a set of cells with the following criteria:

<ol>
	<li>The number of cells in the set has to be greater than <code>1</code> and all cells must be fertile.</li>
	<li>The apex of a pyramid is the topmost cell of the pyramid. The height 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 &lt;= i &lt;= r + h - 1</code> and <code>c - (i - r) &lt;= j &lt;= c + (i - r)</code>.</li>
</ol>

An inverse pyramidal plot of land can be defined as a set of cells with similar criteria:

<ol>
	<li>The number of cells in the set has to be greater than <code>1</code> and all cells must be fertile.</li>
	<li>The apex of an inverse pyramid is the bottommost cell of the inverse pyramid. The height 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 &lt;= i &lt;= r</code> and <code>c - (r - i) &lt;= j &lt;= c + (r - i)</code>.</li>
</ol>

Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.
<img src="https://assets.leetcode.com/uploads/2021/11/08/image.png" style="width: 700px; height: 156px;" />
Given a 0-indexed <code>m x n</code> binary matrix <code>grid</code> representing the farmland, return the total number of pyramidal and inverse pyramidal plots that can be found in <code>grid</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/22/1.JPG" style="width: 575px; height: 109px;" />
<pre>
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.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/22/2.JPG" style="width: 502px; height: 120px;" />
<pre>
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.
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/22/3.JPG" style="width: 676px; height: 148px;" />
<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 1000</code></li>
	<li><code>1 &lt;= m * n &lt;= 105</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

countPyramids

Count Fertile Pyramids in a Land

Count Square Submatrices with All Ones

count-square-submatrices-with-all-ones

统计全为 1 的正方形子矩阵

Get Biggest Three Rhombus Sums in a Grid

get-biggest-three-rhombus-sums-in-a-grid

矩阵中最大的三个菱形和

Array

Dynamic Programming

Matrix

有一个 矩形网格&nbsp;状的农场，划分为&nbsp;<code>m</code>&nbsp;行&nbsp;<code>n</code>&nbsp;列的单元格。每个格子要么是 肥沃的&nbsp;（用 <code>1</code>&nbsp;表示），要么是 贫瘠&nbsp;的（用 <code>0</code>&nbsp;表示）。网格图以外的所有与格子都视为贫瘠的。

农场中的&nbsp;金字塔&nbsp;区域定义如下：

<ol>
	<li>区域内格子数目 大于&nbsp;<code>1</code>&nbsp;且所有格子都是 肥沃的&nbsp;。</li>
	<li>金字塔 顶端&nbsp;是这个金字塔 最上方&nbsp;的格子。金字塔的高度是它所覆盖的行数。令&nbsp;<code>(r, c)</code>&nbsp;为金字塔的顶端且高度为 <code>h</code>&nbsp;，那么金字塔区域内包含的任一格子&nbsp;<code>(i, j)</code>&nbsp;需满足&nbsp;<code>r &lt;= i &lt;= r + h - 1</code>&nbsp;且&nbsp;<code>c - (i - r) &lt;= j &lt;= c + (i - r)</code>&nbsp;。</li>
</ol>

一个 倒金字塔&nbsp;类似定义如下：

<ol>
	<li>区域内格子数目 大于&nbsp;<code>1</code>&nbsp;且所有格子都是 肥沃的&nbsp;。</li>
	<li>倒金字塔的 顶端&nbsp;是这个倒金字塔 最下方&nbsp;的格子。倒金字塔的高度是它所覆盖的行数。令&nbsp;<code>(r, c)</code>&nbsp;为金字塔的顶端且高度为 <code>h</code>&nbsp;，那么金字塔区域内包含的任一格子&nbsp;<code>(i, j)</code>&nbsp;需满足&nbsp;<code>r - h + 1 &lt;= i &lt;= r</code> 且 <code>c - (r - i) &lt;= j &lt;= c + (r - i)</code>&nbsp;。</li>
</ol>

下图展示了部分符合定义和不符合定义的金字塔区域。黑色区域表示肥沃的格子。

<img src="https://assets.leetcode.com/uploads/2021/11/08/image.png" style="width: 700px; height: 156px;">

给你一个下标从 0&nbsp;开始且大小为 <code>m x n</code>&nbsp;的二进制矩阵&nbsp;<code>grid</code>&nbsp;，它表示农场，请你返回 <code>grid</code>&nbsp;中金字塔和倒金字塔的&nbsp;总数目&nbsp;。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/eg11.png" style="width: 200px; height: 102px;">&nbsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/exa12.png" style="width: 200px; height: 102px;">&nbsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/exa13.png" style="width: 200px; height: 102px;">

<pre>输入：grid = [[0,1,1,0],[1,1,1,1]]
输出：2
解释：
2 个可能的金字塔区域分别如上图蓝色和红色区域所示。
这个网格图中没有倒金字塔区域。
所以金字塔区域总数为 2 + 0 = 2 。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/eg21.png" style="width: 180px; height: 122px;">&nbsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/exa22.png" style="width: 180px; height: 122px;">&nbsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/exa23.png" style="width: 180px; height: 122px;">

<pre>输入：grid = [[1,1,1],[1,1,1]]
输出：2
解释：
金字塔区域如上图蓝色区域所示，倒金字塔如上图红色区域所示。
所以金字塔区域总数目为 1 + 1 = 2 。
</pre>

示例 3：

<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/eg3.png" style="width: 149px; height: 150px;">

<pre>输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：0
解释：
网格图中没有任何金字塔或倒金字塔区域。
</pre>

示例 4：

<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/eg41.png" style="width: 180px; height: 144px;">&nbsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/eg42.png" style="width: 180px; height: 144px;">&nbsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/eg43.png" style="width: 180px; height: 144px;">&nbsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/10/23/eg44.png" style="width: 180px; height: 144px;">

<pre>输入：grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
输出：13
解释：
有 7 个金字塔区域。上图第二和第三张图中展示了它们中的 3 个。
有 6 个倒金字塔区域。上图中最后一张图展示了它们中的 2 个。
所以金字塔区域总数目为 7 + 6 = 13.
</pre>

&nbsp;

提示：

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 1000</code></li>
	<li><code>1 &lt;= m * n &lt;= 105</code></li>
	<li><code>grid[i][j]</code>&nbsp;要么是&nbsp;<code>0</code>&nbsp;，要么是&nbsp;<code>1</code> 。</li>
</ul>