包含网格点的矩形数

Question

我想知道网格中包含特定点的矩形的数量（不是用于计算所有矩形点的算法）。

例如。设网格为 ->

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

现在假设我们希望“11”始终出现在该网格可能出现的所有矩形内。所以可能的矩形将是 -

11

11 12

11 12 13

11 12 13 14

11 12 13 14 15

11    
21

11
21    
31

11 12    
21 22

依此类推...为此，共有 15 个可能的矩形。

如何计算网格中给定点的此类矩形总数？

Answer 1

让我们看看这样的网格：

+--+--+--+--+--+
|11|12|13|14|15|
+--+--+--+--+--+
|21|22|23|24|25|
+--+--+--+--+--+
|31|32|33|34|35|
+--+--+--+--+--+

每个+都是一个矩形角点，每个矩形可以用两个相对的点来描述，一个是左上角，一个是右下角。
如果我们想找到包含给定字段 pq 的所有矩形，我们需要找到左上角点位于我们字段的上方和左侧且右下角点位于下方和右侧的所有矩形领域的。
所有左上角点和所有右下角点将再次产生两个网格：

pq = 22
+--+
|11|12 13 14 15
+--+
 21 22 23 24 25
      +--+--+--+
 31 32|33|34|35|
      +--+--+--+

左上角的大小很容易计算：p*q
右下角的大小可以用以下公式计算：(r+1-p)*(c+1-q)
其中 r 是行数，c 是列数（在本例中分别为 3 和 5）。

最后包含pq的矩形个数为：
p*q * (r+1-p)*(c+1-q)

对于 pq=11 这将是：1*1 * (3+1-1)*(5+1-1) = 1 * 3*5 = 15

Number of rectangles containing a point of grid