主題
題目連結：
題目意譯：
一位農夫有著一塊矩形網格狀的土地，其有著 m 列以及 n 行的單位格子。每個格子要嘛肥沃（以一個 1 表示）、要嘛貧瘠（以一個 0 表示）。所有在網格之外的格子視為貧瘠的。
一個金字塔型的土地可以由一個格子之集合來定義，其按照以下規範：
集合中的格子數必須大於 1 且所有格子必須為肥沃的。
一個金字塔的頂端為金字塔最上面的格子。金字塔的高度為其覆蓋到的列數。令 (r, c) 為一金字塔的頂端，且其高度為 h。則其圖形將由格子們 (i, j) 所組成，其中 r ≦ i ≦ r + h - 1 且 c - (i - r) ≦ j ≦ c + (i - r)。
一個反金字塔型的土地可以由一個格子之集合來定義，其按照相似的規範：
集合中的格子數必須大於 1 且所有格子必須為肥沃的。
一個金字塔的頂端為金字塔最下面的格子。金字塔的高度為其覆蓋到的列數。令 (r, c) 為一金字塔的頂端，且其高度為 h。則其圖形將由格子們 (i, j) 所組成，其中 r - h + 1 ≦ i ≦ r 且 c - (r - i) ≦ j ≦ c + (r - i)。
以下是一些合法（Valid）以及不合法（Invalid）的金字塔（以及反金字塔）型的範例。黑色格子代表的是肥沃的格子。
給定一個索引值從 0 開始的 m × n 二元矩陣 grid 代表著農地，回傳 grid 中可以找出的金字塔型以及反金字塔型之數量。
限制：
m == grid.length
n == grid[i].length
1 ≦ m, n ≦ 1000
1 ≦ m × n ≦ 10 ^ 5
grid[i][j] 只會是 0 或是 1。
範例測資：
範例 1：
輸入： grid = [[0,1,1,0],[1,1,1,1]]
輸出： 2
解釋： 2 個可能的金字塔型以藍色以及紅色分別顯示於上圖。
這個網格中沒有任何反金字塔型。
因此金字塔型和反金字塔型的總量為 2 + 0 = 2。
範例 2：
輸入： grid = [[1,1,1],[1,1,1]]
輸出： 2
解釋： 金字塔型以藍色表示，而反金字塔型以紅色表示。
因此總量為 1 + 1 = 2。
Hence the total number of plots is 1 + 1 = 2.
範例 3：
輸入： 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。
解題思維：
可以看到一個金字塔型在各個不同高度值時，其格子總數為
1、
1 + 3、
1 + 3 + 5、
1 + 3 + 5 + 7、
……
因此，從頂端往下 r 列（不含頂端）將會比上一列多 2r + 1 個格子。
而當一個金字塔的頂端位於 (r, c) 時，可以根據題意看到往下每一列的最左和最右的位置依序為
(r + 1, c - 1) 和 (r + 1, c + 1) 、
(r + 2, c - 2) 和 (r + 2, c + 2) 、
(r + 3, c - 3) 和 (r + 3, c + 3) 、
……
所以我們可以看到當兩金字塔的頂端重合時，高度值較小的金字塔將會包含於高度值較大的之中。因此如果已知高度值較小的「偽」金字塔有格子是 0的話，則可以知道高度值增加地再大，其所形成的金字塔皆不合法。
因此，我們就有一個非常自然的策略來統計金字塔的數量（統計反金字塔型也是類似方式）——也就是窮舉金字塔的頂端之位置，並往下沿展（即增加高度），直到不能沿展為止（碰到有一列的底部包含到 0 之格子，或是單純地碰到了邊界）。
那在往下沿展一列時要如何快速地知道該列最左到最右之位置之格子皆為 1 呢？很簡單，根據最上面格子數增長之規則（每往下 k 列有 2k + 1 個格子）以及最左和最右的位置依序為
(r + k, c - k) 和 (r + k, c + k)
再搭配前綴和（Prefix Sums）之概念（如這題）便可以計算出快速地計算出 (r + k, c - k) ～ (r + k, c + k) 間有幾個格子為 1（假設是 X 個）。如果 X = 2k + 1，則代表著這個新長的一列全部都是 1，代表我們得到了一個合法的新金字塔（前提是前面生成的也是合法的金字塔）；反之，則得到了一個不合法的金字塔，接著再增加高度值也毫無意義。
而時間複雜度的方面（為了方便起見，令 m = n），可以看到單看一列的話，每一列成為某個金字塔的「底部」的次數將會被 O(n ^ 2) 限制住（也就是在同一列上選「最左」與「最右」兩個位置的方法數），而列數有 n 個。因此時間為 O(n ^ 3)，如果是符合原先題目的變數條件，則可推得 O(mn × min(m, n))。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
