{"id":8820,"date":"2021-11-27T09:42:32","date_gmt":"2021-11-27T17:42:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8820"},"modified":"2021-11-27T12:21:44","modified_gmt":"2021-11-27T20:21:44","slug":"leetcode-2088-count-fertile-pyramids-in-a-land","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-2088-count-fertile-pyramids-in-a-land\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2088. Count Fertile Pyramids in a Land"},"content":{"rendered":"\n

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

A pyramidal plot<\/strong> of land can be defined as a set of cells with the following criteria:<\/p>\n\n\n\n

  1. The number of cells in the set has to be greater than <\/strong>1<\/code> and all cells must be fertile<\/strong>.<\/li>
  2. The apex<\/strong> of a pyramid is the topmost<\/strong> cell of the pyramid. The height<\/strong> of a pyramid is the number of rows it covers. Let (r, c)<\/code> be the apex of the pyramid, and its height be h<\/code>. Then, the plot comprises of cells (i, j)<\/code> where r <= i <= r + h - 1<\/code> and<\/strong> c - (i - r) <= j <= c + (i - r)<\/code>.<\/li><\/ol>\n\n\n\n

    An inverse pyramidal plot<\/strong> of land can be defined as a set of cells with similar criteria:<\/p>\n\n\n\n

    1. The number of cells in the set has to be greater than <\/strong>1<\/code> and all cells must be fertile<\/strong>.<\/li>
    2. The apex<\/strong> of an inverse pyramid is the bottommost<\/strong> cell of the inverse pyramid. The height<\/strong> of an inverse pyramid is the number of rows it covers. Let (r, c)<\/code> be the apex of the pyramid, and its height be h<\/code>. Then, the plot comprises of cells (i, j)<\/code> where r - h + 1 <= i <= r<\/code> and<\/strong> c - (r - i) <= j <= c + (r - i)<\/code>.<\/li><\/ol>\n\n\n\n

      Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.<\/p>\n\n\n\n

      \"\"\/<\/figure>\n\n\n\n

      Given a 0-indexed<\/strong> m x n<\/code> binary matrix grid<\/code> representing the farmland, return the total number<\/strong> of pyramidal and inverse pyramidal plots that can be found in<\/em> grid<\/code>.<\/p>\n\n\n\n

      Example 1:<\/strong><\/p>\n\n\n\n

      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      Input:<\/strong> grid = [[0,1,1,0],[1,1,1,1]]\nOutput:<\/strong> 2\nExplanation:<\/strong>\nThe 2 possible pyramidal plots are shown in blue and red respectively.\nThere are no inverse pyramidal plots in this grid. \nHence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.\n<\/pre>\n\n\n\n
      Example 2:<\/strong><\/p>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      Input:<\/strong> grid = [[1,1,1],[1,1,1]]\nOutput:<\/strong> 2\nExplanation:<\/strong>\nThe pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red. \nHence the total number of plots is 1 + 1 = 2.\n<\/pre>\n\n\n\n
      Example 3:<\/strong><\/p>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      Input:<\/strong> grid = [[1,0,1],[0,0,0],[1,0,1]]\nOutput:<\/strong> 0\nExplanation:<\/strong>\nThere are no pyramidal or inverse pyramidal plots in the grid.\n<\/pre>\n\n\n\n
      Example 4:<\/strong><\/p>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
      Input:<\/strong> grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]\nOutput:<\/strong> 13\nExplanation:<\/strong>\nThere are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.\nThere are 6 inverse pyramidal plots, 2 of which are shown in the last figure.\nThe total number of plots is 7 + 6 = 13.\n<\/pre>\n\n\n\n
      Constraints:<\/strong><\/p>\n\n\n\n
      • m == grid.length<\/code><\/li>
      • n == grid[i].length<\/code><\/li>
      • 1 <= m, n <= 1000<\/code><\/li>
      • 1 <= m * n <= 105<\/sup><\/code><\/li>
      • grid[i][j]<\/code> is either 0<\/code> or 1<\/code>.<\/li><\/ul>\n\n\n\n
        Solution: DP<\/strong><\/h2>\n\n\n\n
        Let dp[i][j] be the height+1 of a Pyramid tops at i, j
        dp[i][j] = min(dp[i+d][j – 1], dp[i + d][j + 1]) + 1 if dp[i-1][j] else grid[i][j] <\/p>\n\n\n\n
        Time complexity: O(mn)
        Space complexity: O(mn)<\/p>\n\n\n\n
        \n
        Python<\/h2>\n
        \n\n
        \n# Author: Huahua\nclass Solution:\n  def countPyramids(self, grid: List[List[int]]) -> int:\n    m = len(grid)\n    n = len(grid[0])\n    ans = 0\n\n    @cache\n    def dp(i: int, j: int, d: int) -> int:\n      if grid[i][j] and 0 <= i + d < m and 0 < j < n - 1 and grid[i + d][j]:\n        return min(dp(i + d, j - 1, d), dp(i + d, j + 1, d)) + 1\n      return grid[i][j]\n    \n    for i, j in product(range(m), range(n)):\n      ans += max(0, dp(i, j, 1) - 1)\n      ans += max(0, dp(i, j, -1) - 1)\n    \n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
        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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217],"class_list":["post-8820","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8820","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8820"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8820\/revisions"}],"predecessor-version":[{"id":8824,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8820\/revisions\/8824"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8820"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8820"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8820"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}