aboutsummaryrefslogtreecommitdiff
path: root/count_fertile_pyramids_land.py
blob: 8317f409778ad233873402e1f777fd38637f0398 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 2088. Count Fertile Pyramids in a Land
from itertools import product

"""
a farmer has a rectangular grid of land with 'm' rows and 'n' columns that
can be divided into unit cells. each cell is either fertile (represented by a
1) or barren (represented by a 0). all cells outside the grid are considered
barren. a pyamidal plot of land can be defined as a set of cells with the
following criteria: the number of cells in the set has to be greater than 1
and all cells must be fertile, and the apex of the pyramid is the topmost
cell of the pyramid. the height of a pyramid is the number of rows it covers.
let '(r, c)' be the apex of the pyramid and its height be 'h'. given a
0-indexed 'm x n' binary matrix 'grid' representing the farmland, return the
total number of pyramidal and inverse pyramidal plots that can be found in
'grid'.
"""


class Solution(object):
    def countPyramids(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n, ans = len(grid), len(grid[0]), 0

        def dp(i, j, dir):
            if (
                grid[i][j] == 1
                and 0 <= i + dir < m
                and j > 0
                and j + 1 < n
                and grid[i + dir][j] == 1
            ):
                return min(dp(i + dir, j - 1, dir), dp(i + dir, j + 1, dir)) + 1
            return grid[i][j]

        for i, j in product(range(m), range(n)):
            ans += max(0, dp(i, j, 1) - 1)
            ans += max(0, dp(i, j, -1) - 1)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.countPyramids(grid=[[0, 1, 1, 0], [1, 1, 1, 1]]))
    print(obj.countPyramids(grid=[[1, 1, 1], [1, 1, 1]]))
    print(
        obj.countPyramids(
            grid=[[1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 0, 0, 1]]
        )
    )