给定一个m x n网格，在这样的网格上存在多少个独特的子矩形？
例如，
1 x 1网格有 1 个子矩形。
1 x 2网格有 3 个子矩形。
我正在寻找一个可用于直接计算现有子矩形数量的通用公式。
问问题
22205 次
7 回答
19
答案是m(m+1)n(n+1)/4。
矩形由其在 x 轴和 y 轴上的两个投影定义。
x 轴上的投影：对 (a,b) 的数量使得 1 <= a <= b <= m = m(m+1)/2
y 轴同上
于 2013-07-29T15:18:16.453 回答
16
与@Thomash 提供的答案相同，但有更多解释，为后代发布：
如果您可以在一维中解决此问题，则很容易将其移动到二维中。
让我们看一个 1x5：
5 1x1 squares
+4 1x2 squares
+3 1x3 squares
+2 1x4 squares
+1 1x5 squares = 15 squares.
这个公式很简单：sum = n(1 + n)/ 2. 在 5 的情况下，您需要 5(1+5)/2 = 15。
所以，要得到你的答案，只需对 n 和 m 执行此操作，然后将它们相乘：
sumN = n(1+n)/2
sumM = m(1+m)/2
totalRectangles = nm(1+n)(1+m)/4
于 2013-07-29T15:24:05.613 回答
5
我找到了一个很好的解决方案，
让我们看看网格的表格边框。
为了创建一个矩形，我们需要在边框上设置四个点。
2点水平和2点垂直
例如 (n = 4, , m = 5)
注意选择 N + 1 和 M + 1 因为我们看的是边界而不是矩形本身
这是一个选择的示例：
我们可以使用二项式公式计算选择 2 个水平点和 2 个垂直点的所有可能选择：
于 2016-08-18T14:34:00.440 回答
3
为此，假设您有m列和n行：
. . . .
. . . .
. . . .
在上面的网格中，m是 4 和n3。假设您需要知道如果选择左上角可以形成多少个矩形。如果您选择左上角，即
* . . .
. . . .
. . . .
您3在右边有点选择，在底部有 2 点可供选择，因此总组合为：3*2 = 6。
因此，您可以形成的矩形总数将对应于从(0, 0)（top left假设是0, 0）直到每个点的矩形总数(m-1, n-1)。
如果你试图找到这个的总和：
[(m-1)*(n-1) + (m-2)*(n-1) + (m-3)*(n-1) ... + (n-1)] +
[(m-1)*(n-2) + (m-2)*(n-2) ... + 1*(n-2)] +
[(m-1)*(n-3) + (m-2)*(n-3) ... + 1*(n-3)] +
...
这等于
(n-1)*(1 + 2 + .. + m-1)
+
(n-2)*(1 + 2 + .. + m-1)
+
.
.
+
1*(1 + 2 + ... + m-1)
所以你得到
(1 + 2 + ... + n-1) * ( 1 + 2 + 3 ... + m-1)
= mn(n-1)(m-1)/4
因为你m的n情况不是点数，而是形成的线段数。上式可以转化为：
m = m + 1
&
n = n + 1
它变成了
(n+1)(m+1)mn / 4
于 2013-07-29T15:35:39.697 回答
2
另一种解决方案，
在 am*n 网格中，我们有 m+1 条线和 n+1 条线相交。
我们使用这个事实，可以通过选择这些线与另一个不在水平或垂直线上的点之间的交点来形成一个矩形。
因此，选择交点的方法数量为 (m+1)(n+1)。随后选择第二个点的方式数是[这是选择交叉点的方式数，不包括同一水平和垂直线上的点]是((m+1)(n+1)-nm-1 )
现在考虑一个 1x1 网格，我们使用这个网格可以被 4 个点唯一地计算 4 次的事实。
因此可以形成的矩形总数为[(m+1)(n+1)((m+1)(n+1)-nm-1)]/4
可以进一步简化为[(m+1)(n+1)(m)(n)]/4
于 2017-06-21T14:22:11.667 回答
1
有 ((m+1) m n*(n+1))/4 个矩形，包括正方形 [矩形子集]
于 2020-11-04T20:01:25.237 回答
0
正确答案应该是(m(m+1)n(n+1))/4减去矩形网格中的正方形数。
于 2017-05-29T12:20:49.540 回答