<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 &lt;= i &lt;= r + h - 1</code> <strong>and</strong> <code>c - (i - r) &lt;= j &lt;= 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 &lt;= i &lt;= r</code> <strong>and</strong> <code>c - (r - i) &lt;= j &lt;= 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>
<img src="https://assets.leetcode.com/uploads/2021/11/08/image.png" style="width: 700px; height: 156px;" />
<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>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/22/1.JPG" style="width: 575px; height: 109px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[1,1,1,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/22/2.JPG" style="width: 502px; height: 120px;" />
<pre>
<strong>Input:</strong> grid = [[1,1,1],[1,1,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/22/3.JPG" style="width: 676px; height: 148px;" />
<pre>
<strong>Input:</strong> grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
<strong>Output:</strong> 13
<strong>Explanation:</strong> 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>

<p>&nbsp;</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 &lt;= m, n &lt;= 1000</code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        pass
        '''
        문제 예시가 좀 헷갈림. note를 볼것. 
        '''


















class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        dp1, dp2 = copy.deepcopy(grid), copy.deepcopy(grid)
        dp = copy.deepcopy(grid)

        ans = 0
        for y in range(m-2, -1, -1):
            for x in range(1, n-1):
                if grid[y][x] > 0 and grid[y+1][x] > 0:
                    if grid[y+1][x-1] and grid[y+1][x+1] and grid[y+1][x]:
                        dp1[y][x] = min(dp1[y+1][x-1], dp1[y+1][x+1]) + 1
                        ans += dp1[y][x] - 1
        print(ans)
        for y in range(1, m):
            for x in range(1, n-1):
                if grid[y][x] > 0 and grid[y-1][x] > 0:
                    if grid[y-1][x-1] and grid[y-1][x+1] and grid[y-1][x]:
                        dp2[y][x] = min(dp2[y-1][x-1], dp2[y-1][x+1]) + 1
                        ans += dp2[y][x] - 1
        print(ans)
        return ans



















class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        dp_up = copy.deepcopy(grid)
        dp_down = copy.deepcopy(grid)
        m, n = len(grid), len(grid[0])
        cnt = 0

        for y in range(m-2, -1, -1):
            for x in range(1, n-1):
                if dp_up[y][x]:
                    if dp_up[y+1][x] and dp_up[y+1][x-1] and dp_up[y+1][x+1]:
                        dp_up[y][x] = min(dp_up[y+1][x-1], dp_up[y+1][x+1]) + 1
                        cnt += dp_up[y][x] - 1
        
        for y in range(1, m):
            for x in range(1, n-1):
                if dp_down[y][x]:
                    if dp_down[y-1][x] and dp_down[y-1][x-1] and dp_down[y-1][x+1]:
                        dp_down[y][x] = min(dp_down[y-1][x-1], dp_down[y-1][x+1]) + 1
                        cnt += dp_down[y][x] - 1
        
        return cnt





class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        dp_up = copy.deepcopy(grid)
        dp_down = copy.deepcopy(grid)

        cnt = 0
        m, n = len(grid), len(grid[0])
        for y in range(m-2, -1, -1):
            for x in range(1, n-1):
                if grid[y][x]:
                    if grid[y+1][x] and grid[y+1][x-1] and grid[y+1][x+1]:
                        dp_up[y][x] = min(dp_up[y+1][x-1], dp_up[y+1][x+1]) + 1
                        cnt += dp_up[y][x] - 1
        for y in range(1, m):
            for x in range(1, n-1):
                if grid[y][x]:
                    if grid[y-1][x] and grid[y-1][x-1] and grid[y-1][x+1]:
                        dp_down[y][x] = min(dp_down[y-1][x-1], dp_down[y-1][x+1]) + 1
                        cnt += dp_down[y][x] - 1
        return cnt

































class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp_up = copy.deepcopy(grid)
        dp_down = copy.deepcopy(grid)

        cnt = 0
        for y in range(m-2, -1, -1):
            for x in range(1, n-1):
                if grid[y][x]:
                    if grid[y+1][x] and grid[y+1][x-1] and grid[y+1][x+1]:
                        dp_up[y][x] = min(dp_up[y+1][x-1], dp_up[y+1][x+1]) + 1
                        cnt += dp_up[y][x] - 1
        for y in range(1, m):
            for x in range(1, n-1):
                if grid[y][x]:
                    if grid[y-1][x] and grid[y-1][x-1] and grid[y-1][x+1]:
                        dp_down[y][x] = min(dp_down[y-1][x-1], dp_down[y-1][x+1]) + 1
                        cnt += dp_down[y][x] - 1
        return cnt


class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        #dp_up = grid.copy()
        #dp_down = grid.copy()

        dp_up = copy.deepcopy(grid)
        dp_down = copy.deepcopy(grid)
        # dp stores height of the maximum pyramid
        ans = 0
        m, n = len(grid), len(grid[0])
        for y in range(m-2, -1, -1):
            for x in range(1, n-1):
                if dp_up[y][x]:
                    if dp_up[y+1][x-1] and dp_up[y+1][x] and dp_up[y+1][x+1]:
                        dp_up[y][x] = min(dp_up[y+1][x-1], dp_up[y+1][x+1]) + 1
                        ans += dp_up[y][x] - 1
        for y in range(1, m):
            for x in range(1, n-1):
                if dp_down[y][x]:
                    if dp_down[y-1][x-1] and dp_down[y-1][x] and dp_down[y-1][x+1]:
                        dp_down[y][x] = min(dp_down[y-1][x-1], dp_down[y-1][x+1]) + 1
                        ans += dp_down[y][x] - 1
        return ans


class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        dp_up = copy.deepcopy(grid)
        dp_down = copy.deepcopy(grid)
        cnt = 0

        m, n = len(grid), len(grid[0])
        for y in range(m-2, -1, -1):
            for x in range(1, n-1):
                if grid[y][x] == 1:
                    if grid[y+1][x-1] and grid[y+1][x] and grid[y+1][x+1]:
                        dp_up[y][x] = min(dp_up[y+1][x-1], dp_up[y+1][x+1]) + 1
                        #dp_up[y][x] = min(dp_up[y+1][x-1], dp_up[y+1][x+1]) + 1  
                        cnt += dp_up[y][x] - 1
        for y in range(1, m):
            for x in range(1, n-1):
                if grid[y][x] == 1:
                    if grid[y-1][x-1] and grid[y-1][x] and grid[y-1][x+1]:
                        dp_down[y][x] = min(dp_down[y-1][x-1], dp_down[y-1][x+1]) + 1
                        #dp_down[y][x] = min(dp_down[y-1][x-1], dp_down[y-1][x+1]) + 1
                        cnt += dp_down[y][x] - 1

        return cnt
20200