Ile subrectangle istnieje na siatce m x n

Question

Biorąc pod uwagę siatkę m x n, ile unikalnych pod-prostokątów istnieje na takiej siatce?

Przykładowo

1 x 1 siatki 1 ma sub-prostokąta.

1 x 2 siatka ma 3 pod-prostokąty.

Szukam ogólnej formuły, która może być używana do bezpośredniego obliczania liczby istniejącego pod-prostokąta.

Answer 1

Odpowiedź brzmi: m(m+1)n(n+1)/4.

Prostokąt definiowany jest przez dwa rzuty na osi X i na osi Y.

występ na osi odciętych: numer par (a, b), tak że jeden < = a < = B < = m = M (M + 1)/2

idem na osi y

Answer 2

Taka sama odpowiedź jak w przypadku @Thomash, ale z nieco większą ilością wyjaśnień, publikowanie dla potomności:

Jeśli uda Ci się to zrozumieć w jednym wymiarze, możesz łatwo przenieść go na dwa wymiary. wygląd

Miejmy na 1x5:

5 1x1 squares 
+4 1x2 squares 
+3 1x3 squares 
+2 1x4 squares 
+1 1x5 squares = 15 squares. 

Formuła jest prosta: sum = n(1 + n)/ 2. W przypadku 5, chcesz 5 (1 + 5)/2 = 15.

Tak więc, aby uzyskać odpowiedź, po prostu zrób to dla n i m, i pomnożyć je:

sumN = n(1+n)/2 
sumM = m(1+m)/2 
totalRectangles = nm(1+n)(1+m)/4 

Answer 3

Dla to pozwala zakładać masz m kolumn i wierszy n:

. . . . 
. . . . 
. . . . 

podano siatce m jest 4 i n to 3. powiedzmy trzeba wiedzieć ile prostokąt można tworzyć w przypadku wybrania lewym górnym punkcie . W przypadku wybrania opcji lewy górny róg-tj

* . . . 
. . . . 
. . . . 

Musisz mieć 3 punkt wyboru w prawo i 2 punkty do wyboru na dole, więc całkowite kombinacje są: 3*2 = 6.

Zatem łączna liczba prostokąt można tworzyć będzie odpowiadać ogólnej liczby prostokątów na każdy punkt startu z (0, 0) (top left zakładać być 0, 0) aż (m-1, n-1).

Jeśli próbujesz znaleźć sumowanie to:

[(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)] + 
... 

która jest równa

(n-1)*(1 + 2 + .. + m-1) 
+ 
(n-2)*(1 + 2 + .. + m-1) 
+ 
. 
. 
+ 
1*(1 + 2 + ... + m-1) 

Więc masz

(1 + 2 + ... + n-1) * (1 + 2 + 3 ... + m-1) 
= mn(n-1)(m-1)/4 

Od m i n to sprawa nie są liczba punktów, ale liczba utworzonych segmentów linii. Powyższy wzór można przekształcić:

m = m + 1 
& 
n = n + 1 

I staje

(n+1)(m+1)mn/4 

Answer 4

Znalazłem ładne rozwiązanie,
Spójrzmy na granicach stołowych siatki.
Aby utworzyć prostokąt, potrzebujemy czterech punktów na granicach.
2 punkty poziomych i dwie pionowe

na przykład (N = 4, M = 5)
do wiadomości, że wybór na N + 1 i M + 1 Ponieważ wygląda na granicach i nie prostokątów sami

Oto przykład jednego wyboru:

Możemy obliczyć wszystkie możliwe opcje do wyboru 2 pkt poziome i 2 pionowe punktu użyciu dwumianowego wzoru:

Answer 5

Prawidłowa odpowiedź powinna być (m(m+1)n(n+1))/4 minus liczba kwadratów w prostokątnej siatce.

Answer 6

Alternatywnym rozwiązaniem

W m * n siatki mamy M + 1 wierszach i n + 1 przecinających się linii.

Korzystamy z faktu, że prostokąt można utworzyć, wybierając punkt przecięcia między tymi liniami i innym punktem, który nie znajduje się w linii poziomej lub pionowej.

Tak więc, wiele sposobów wyboru punktu przecięcia to (m + 1) (n + 1). , a następnie liczba sposobów wyboru drugiego punktu to [czyli liczba sposobów wyboru punktu przecięcia z wyłączeniem punktów w tej samej linii poziomej i pionowej] to ((m + 1) (n + 1) -nm -1)

Rozważmy teraz kratę 1x1, wykorzystujemy fakt, że tę siatkę można policzyć 4 razy za każdym razem wyjątkowo 4 punktami.

Dlatego też całkowita liczba prostokąty, które mogą osad [(M + 1) (n + 1) ((M + 1) (n + 1) -nm-1)]/4

które można jeszcze bardziej uprościć do [(m + 1) (n + 1) (m) (n)]/4