algorithm - マトリックス内の可能な長方形の数

Question

行列の領域の合計を計算するアルゴリズムを使用しています。そして、より良い結果を得るために合計を事前計算するための解決策を読みました.サイズmXnの2次元マトリックスで可能な長方形(サブMaxtix)の数を計算したいと思います.

順列と組み合わせを使用して解決策を説明できる人はいますか?

Answer 1

最初に最も単純なケースから始めます。

Start with m x n, thats 1 rectangle.
Reduce n by 1, that gives another 2.
Reduce n by 1, that gives another 3.
Reduce n by 1, that gives another 4.

パターンが見えますか？

n が 1 になったら、m から 1 を引き、最初からやり直します。

Start with m-1 x n, thats 2 rectangles.
Reduce n by 1, that gives another 4.
Reduce n by 1, that gives another 6.
Reduce n by 1, that gives another 8.

あなたはまだパターンを見ていますか..？

ここで、m-2、m-3、m-4、...、1 に外挿します。

ここで、最初に n を減らし、次に n を減らします (または、mxn を除くすべての結果を単純に 2 倍にします)。

そして、これらすべての結果の合計があなたの答えです。

Answer 2

これはアルゴリズムではなく、カウントの問題です。1X1 マトリックスと 1X2 2X1 3X2 などの長方形の数を数えてみると、次のようになります。

num_of_rect(mXn) = sum(i*j) for 0<i<m+1; 0<j<n+1

---

パイソンで：

def countRect(n,m):
    return sum([i*j for i in xrange(n+1) for j in xrange(m+1)])

if __name__ == "__main__":
    print countRect(2,3)

与える18

Answer 3

mxn 行列内の任意のサイズの可能な Rectangle の数

mn + (m-1)(n-1) + (m-2)(n-1) + .. + (m-m+1)(n-1) + (m-1)(m-2) + .. + (mm)(nn)

[0,m] の i の合計 { i * j }; [0,n] の j

Answer 4

含める行と列を選択するだけで、 a,b>=2 のすべての長方形 a*b を数えることができます (図を参照)。

C(m,2)*C(n,2)

a>=2 で a*1 の長方形を数えることができます

C(m,2)*n

および 1*b 個の長方形 (b>=2 を介して)

m*C(n,2)

および 1*1 行列:

m*n

したがって、最終的な回答にこれらを追加します。

C(m,2)*C(n,2) + C(m,2)*n + m*C(n,2) + m*n