algorithm - amxn グリッド上にいくつのサブ長方形が存在するか

Question

グリッドが与えられた場合m x n、そのようなグリッド上にいくつの一意のサブ長方形が存在しますか?

例えば、

1 x 1グリッドには 1 つのサブ長方形があります。

1 x 2グリッドには 3 つのサブ長方形があります。

既存のサブ長方形の数を直接計算するために使用できる一般的な式を探しています。

Answer 1

答えはm(m+1)n(n+1)/4です。

長方形は、x 軸と y 軸上の 2 つの射影によって定義されます。

x 軸の射影 : 1 <= a <= b <= m = m(m+1)/2 となるペア (a,b) の数

y軸の同上

Answer 2

@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

Answer 3

良い解決策を見つけました
。グリッドのテーブルの境界線を見てみましょう。
長方形を作成するには、境界線上に 4 つの点が必要です。
水平 2 点、垂直 2 点

例: (n = 4, , m = 5)
選択肢は N + 1 と M + 1 であることに注意してください 長方形自体ではなく、境界を見ているからです

選択の例を次に示します。

二項式を使用して、2 つの水平ポイントと 2 つの垂直ポイントを選択するためのすべての可能な選択肢を計算できます。

Answer 4

正方形を含む((m+1) m n*(n+1))/4 個の長方形があります [長方形のサブセット]