[C++, programare dinamică] Suma unor dreptunghiuri ale unei matrice

Enunț:
Scrieți un program care răspunde eficient la mai multe interogări privind suma unor dreptunghiuri ale unei matrice.

Se noteaza matricea data cu A, cu indici pornind de la i = 1 pana la H, cu j = 1 pana la W.

Fie dreptunghiul a cărui sumă o căutăm cu atributele w, h, i (sau y), j (sau x), unde w este lățimea, h este înălțimea, i este rândul din matrice în care începe dreptunghiul înspre dreapta-jos, j fiind coloana din matrice în care începe dreptunghiul înspre dreapta-jos.

Figura 1
Pentru date de intrare:

5 5 3 4 2 3
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Exista datele de ieșire:

117

Dreptunghiuri de la  X = 4, Y = 3
B[3][4][1][1] = 14    B[3][4][1][2] = 33    B[3][4][1][3] = 57   
B[3][4][2][1] = 29    B[3][4][2][2] = 68    B[3][4][2][3] = 117   

Se observa că i coboară de la 1 (sus, primul rând) și j merge de la 1 la dreapta (de la stânga, prima coloană). La i se adună h și la j se adună w.

În datele de intrare de mai sus, 5x5 este dimensiunea matricei din ultimele 5 randuri, (3, 4) este punctul de pornire al dreptunghiului a carui suma o cautam si (2, 3) sunt dimensiunile dreptunghiului (latime 2, inaltime 3).

Din datele de intrare rezultă că matricea rezultat, notata B, va avea 4 dimensiuni:

 B[i][j][w][h] = ?

Cazurile de bază ale recurenței sunt:

  • B[i][j][0][h] = B[i][j][w][0] = 0;
  • B[i][j][1][1] = A[i][j].

Analizăm posibilele cazuri de bază ale recurenței:

  1. i = 1
    1. j = 1
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?
    2. j = ?
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?
  2. i = ?
    1. j = 1
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?
    2. j = ?
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?
Combinațiile posibile sunt următoarele (prin ? am notat valori diferite de 0 și 1 și prin „f.g.”, formula generală):

i = 1, j = 1, w = 0, h = 0 => 0
i = 1, j = 1, w = 0, h = 1 => 0
i = 1, j = 1, w = 0, h = ? => 0
i = 1, j = 1, w = 1, h = 0 => 0
i = 1, j = 1, w = 1, h = 1 => A[1][1]
i = 1, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = 1, w = ?, h = 0 => 0
i = 1, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = 1, j = ?, w = 0, h = 0 => 0
i = 1, j = ?, w = 0, h = 1 => 0
i = 1, j = ?, w = 0, h = ? => 0
i = 1, j = ?, w = 1, h = 0 => 0
i = 1, j = ?, w = 1, h = 1 => A[1][j]
i = 1, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = ?, w = ?, h = 0 => 0
i = 1, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = 1, w = 0, h = 0 => 0
i = ?, j = 1, w = 0, h = 1 => 0
i = ?, j = 1, w = 0, h = ? => 0
i = ?, j = 1, w = 1, h = 0 => 0
i = ?, j = 1, w = 1, h = 1 => A[i][1]
i = ?, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = 1, w = ?, h = 0 => 0
i = ?, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = ?, w = 0, h = 0 => 0
i = ?, j = ?, w = 0, h = 1 => 0
i = ?, j = ?, w = 0, h = ? => 0
i = ?, j = ?, w = 1, h = 0 => 0
i = ?, j = ?, w = 1, h = 1 => A[i][j]
i = ?, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = ?, w = ?, h = 0 => 0
i = ?, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

Se observa că pt. w = 0 sau h = 0 suma este mereu 0, deci se ignora aceste cazuri în matricea rezultat, nu se calculeaza.
Rămâne:

i = 1, j = 1, w = 1, h = 1 => A[1][1]
i = 1, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = 1, j = ?, w = 1, h = 1 => A[1][j]
i = 1, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = 1, w = 1, h = 1 => A[i][1]
i = ?, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = ?, w = 1, h = 1 => A[i][j]
i = ?, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

Din toate posibilele cazuri de recurență le-am ales pe cele utile și am extras mai departe din ele cele cu <submatrice-coloană>:

i = 1, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană

Se combina în:
B[i][j][1][h] = A[i + 1 - 1][j] + A[i + 2 - 1][j] + ... + A[i + h - 1][j].

Se face analog pentru <submatrice-linie>:

i = 1, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie


Se combina în:
B[i][j][w][1] = A[i][j + 1 - 1] + A[i][j + 2 - 1] + ... + A[i][j + w - 1].

Acum avem calculate cazurile:
- B[i][j][1][1];
- B[i][j][w][1];
- B[i][j][1][h];

Mai rămâne de gândit cazul general:
- B[i][j][w][h].

Se ia o submatrice a cărei sumă trebuie calculată (pozițiile se exprimă în funcție de w și h):





B[i][j][w][h] = suma sumelor liniilor sau suma sumelor coloanelor.

1. suma sumelor liniilor (când liniile sunt mai puține decât coloanele sau la fel de multe: h <= w)
B[i][j][w][h] = B[i][j][w][1] + B[i + 1][j][w][1] + B[i + 2][j][w][1] + ... + B[i + h - 1][j][w][1];

2. suma sumelor coloanelor (când coloanele sunt mai puține decât liniile: w < h)
B[i][j][w][h] = B[i][j][1][h] + B[i][j + 1][1][h] + B[i][j + 2][1][h] + ... + B[i][j + w - 1][1][h].

Părțile subliniate din expresiile aldine de mai sus sunt utilizate de mai multe ori în același membru al egalității respective.

Se rezolvă problema cu ce se stie până acum, generând matricea-rezultat de la stânga la dreapta, de sus în jos și se descoperă că ordinea de calculare a valorilor din matrice nu este corectă, se accesează în formula de recurență valori încă necalculate la momentul respectiv.

Mai exact, pentru datele de intrare de mai sus:

5 5 3 4 2 3
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

unde datele au interpretarea de la începutul acestui articol, adică matricea este 5x5, (3,4) este poziția dreptunghiului și (2,3) este dimensiunea lui.

Exemplu:
Pentru calcularea lui B[1][1][2][2] e ceruta valoarea B[1][2][1][2].

Se modifica programul sa afiseze in functie de ce valori e calculata fiecare valoare (nu se poate face foarte vizual deoarece matricea-rezultat are 4 dimensiuni).

În exemplele de mai jos, ce e subliniat nu se schimba în expresia din care face parte, ca indice al matricei:

- când se iau coloane care alcatuiesc dreptunghiul:
B[1][1][2][2] = B[1][1][1][2] + B[1][2][1][2]
B[1][1][2][3] = B[1][1][1][3] + B[1][2][1][3]

- când se iau rânduri:
B[1][1][3][2] = B[1][1][3][1] + B[2][1][3][1]

Dar înainte de a face decizia în program „care caz din cele 2 de mai sus ale formulei generale să utilizez” trebuie să se aibă valorile necesare calculate, deci să se știe în ce ordine se calculează valorile de la început.

În final, se observă în datele de ieșire că toate valorile care depind de altceva decât de valorile matricei de intrare A au valoare nedefinită.

Se incearca să se calculeze mai întâi valorile matricei B care se pot calcula în funcție doar de A.

După ce am făcut asta, se observă că restul valorilor se calculează în ordine corectă, nemaifiind nici o valoare nedefinită în matricea rezultat.

Funcția suma calculeaza ce se poate mai intai si de asta in final poate calcula tot (parcurge matricea de mai multe ori, de fiecare data din stanga sus pana in dreapta jos. Functia test afiseaza calculele toate, in ordine naiva, in consola, inclusiv cele cu valori nedefinite, functia test este un pas intermediar de observatie in rezolvarea problemei.

Se afiseaza in consola cu functia test urmatoarele (pentru aflarea ordinei potrivite de calculare a matricei rezultat):

Se calculeaza.....

B[1][1][1][1] = A[1][1] = 1
B[1][1][1][1] = + A[1][1] = 1
B[1][1][1][2] = + A[1][1] + A[2][1] = 7
B[1][1][1][3] = + A[1][1] + A[2][1] + A[3][1] = 18
B[1][1][1][4] = + A[1][1] + A[2][1] + A[3][1] + A[4][1] = 34
B[1][1][1][5] = + A[1][1] + A[2][1] + A[3][1] + A[4][1] + A[5][1] = 55
B[1][1][2][1] = + A[1][1] + A[1][2] = 3
B[1][1][2][2] = + B[1][1][2][1] + B[2][1][2][1] = -858993457
B[1][1][2][3] = + B[1][1][1][3] + B[1][2][1][3] = -858993442
B[1][1][2][4] = + B[1][1][1][4] + B[1][2][1][4] = -858993426
B[1][1][2][5] = + B[1][1][1][5] + B[1][2][1][5] = -858993405
B[1][1][3][1] = + A[1][1] + A[1][2] + A[1][3] = 6
B[1][1][3][2] = + B[1][1][3][1] + B[2][1][3][1] = -858993454
B[1][1][3][3] = + B[1][1][3][1] + B[2][1][3][1] + B[3][1][3][1] = -1717986914
B[1][1][3][4] = + B[1][1][1][4] + B[1][2][1][4] + B[1][3][1][4] = -1717986886
B[1][1][3][5] = + B[1][1][1][5] + B[1][2][1][5] + B[1][3][1][5] = -1717986865
B[1][1][4][1] = + A[1][1] + A[1][2] + A[1][3] + A[1][4] = 10
B[1][1][4][2] = + B[1][1][4][1] + B[2][1][4][1] = -858993450
B[1][1][4][3] = + B[1][1][4][1] + B[2][1][4][1] + B[3][1][4][1] = -1717986910
B[1][1][4][4] = + B[1][1][4][1] + B[2][1][4][1] + B[3][1][4][1] + B[4][1][4][1] = 1717986926
B[1][1][4][5] = + B[1][1][1][5] + B[1][2][1][5] + B[1][3][1][5] + B[1][4][1][5] = 1717986971
B[1][1][5][1] = + A[1][1] + A[1][2] + A[1][3] + A[1][4] + A[1][5] = 15
B[1][1][5][2] = + B[1][1][5][1] + B[2][1][5][1] = -858993445
B[1][1][5][3] = + B[1][1][5][1] + B[2][1][5][1] + B[3][1][5][1] = -1717986905
B[1][1][5][4] = + B[1][1][5][1] + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] = 1717986931
B[1][1][5][5] = + B[1][1][5][1] + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] + B[5][1][5][1] = 858993471
B[1][2][1][1] = A[1][2] = 2
B[1][2][1][1] = + A[1][2] = 2
B[1][2][1][2] = + A[1][2] + A[2][2] = 9
B[1][2][1][3] = + A[1][2] + A[2][2] + A[3][2] = 21
B[1][2][1][4] = + A[1][2] + A[2][2] + A[3][2] + A[4][2] = 38
B[1][2][1][5] = + A[1][2] + A[2][2] + A[3][2] + A[4][2] + A[5][2] = 60
B[1][2][2][1] = + A[1][2] + A[1][3] = 5
B[1][2][2][2] = + B[1][2][2][1] + B[2][2][2][1] = -858993455
B[1][2][2][3] = + B[1][2][1][3] + B[1][3][1][3] = -858993439
B[1][2][2][4] = + B[1][2][1][4] + B[1][3][1][4] = -858993422
B[1][2][2][5] = + B[1][2][1][5] + B[1][3][1][5] = -858993400
B[1][2][3][1] = + A[1][2] + A[1][3] + A[1][4] = 9
B[1][2][3][2] = + B[1][2][3][1] + B[2][2][3][1] = -858993451
B[1][2][3][3] = + B[1][2][3][1] + B[2][2][3][1] + B[3][2][3][1] = -1717986911
B[1][2][3][4] = + B[1][2][1][4] + B[1][3][1][4] + B[1][4][1][4] = -1717986882
B[1][2][3][5] = + B[1][2][1][5] + B[1][3][1][5] + B[1][4][1][5] = -1717986860
B[1][2][4][1] = + A[1][2] + A[1][3] + A[1][4] + A[1][5] = 14
B[1][2][4][2] = + B[1][2][4][1] + B[2][2][4][1] = -858993446
B[1][2][4][3] = + B[1][2][4][1] + B[2][2][4][1] + B[3][2][4][1] = -1717986906
B[1][2][4][4] = + B[1][2][4][1] + B[2][2][4][1] + B[3][2][4][1] + B[4][2][4][1] = 1717986930
B[1][2][4][5] = + B[1][2][1][5] + B[1][3][1][5] + B[1][4][1][5] + B[1][5][1][5] = 1717986976
B[1][3][1][1] = A[1][3] = 3
B[1][3][1][1] = + A[1][3] = 3
B[1][3][1][2] = + A[1][3] + A[2][3] = 11
B[1][3][1][3] = + A[1][3] + A[2][3] + A[3][3] = 24
B[1][3][1][4] = + A[1][3] + A[2][3] + A[3][3] + A[4][3] = 42
B[1][3][1][5] = + A[1][3] + A[2][3] + A[3][3] + A[4][3] + A[5][3] = 65
B[1][3][2][1] = + A[1][3] + A[1][4] = 7
B[1][3][2][2] = + B[1][3][2][1] + B[2][3][2][1] = -858993453
B[1][3][2][3] = + B[1][3][1][3] + B[1][4][1][3] = -858993436
B[1][3][2][4] = + B[1][3][1][4] + B[1][4][1][4] = -858993418
B[1][3][2][5] = + B[1][3][1][5] + B[1][4][1][5] = -858993395
B[1][3][3][1] = + A[1][3] + A[1][4] + A[1][5] = 12
B[1][3][3][2] = + B[1][3][3][1] + B[2][3][3][1] = -858993448
B[1][3][3][3] = + B[1][3][3][1] + B[2][3][3][1] + B[3][3][3][1] = -1717986908
B[1][3][3][4] = + B[1][3][1][4] + B[1][4][1][4] + B[1][5][1][4] = -1717986878
B[1][3][3][5] = + B[1][3][1][5] + B[1][4][1][5] + B[1][5][1][5] = -1717986855
B[1][4][1][1] = A[1][4] = 4
B[1][4][1][1] = + A[1][4] = 4
B[1][4][1][2] = + A[1][4] + A[2][4] = 13
B[1][4][1][3] = + A[1][4] + A[2][4] + A[3][4] = 27
B[1][4][1][4] = + A[1][4] + A[2][4] + A[3][4] + A[4][4] = 46
B[1][4][1][5] = + A[1][4] + A[2][4] + A[3][4] + A[4][4] + A[5][4] = 70
B[1][4][2][1] = + A[1][4] + A[1][5] = 9
B[1][4][2][2] = + B[1][4][2][1] + B[2][4][2][1] = -858993451
B[1][4][2][3] = + B[1][4][1][3] + B[1][5][1][3] = -858993433
B[1][4][2][4] = + B[1][4][1][4] + B[1][5][1][4] = -858993414
B[1][4][2][5] = + B[1][4][1][5] + B[1][5][1][5] = -858993390
B[1][5][1][1] = A[1][5] = 5
B[1][5][1][1] = + A[1][5] = 5
B[1][5][1][2] = + A[1][5] + A[2][5] = 15
B[1][5][1][3] = + A[1][5] + A[2][5] + A[3][5] = 30
B[1][5][1][4] = + A[1][5] + A[2][5] + A[3][5] + A[4][5] = 50
B[1][5][1][5] = + A[1][5] + A[2][5] + A[3][5] + A[4][5] + A[5][5] = 75
B[2][1][1][1] = A[2][1] = 6
B[2][1][1][1] = + A[2][1] = 6
B[2][1][1][2] = + A[2][1] + A[3][1] = 17
B[2][1][1][3] = + A[2][1] + A[3][1] + A[4][1] = 33
B[2][1][1][4] = + A[2][1] + A[3][1] + A[4][1] + A[5][1] = 54
B[2][1][2][1] = + A[2][1] + A[2][2] = 13
B[2][1][2][2] = + B[2][1][2][1] + B[3][1][2][1] = -858993447
B[2][1][2][3] = + B[2][1][1][3] + B[2][2][1][3] = -858993427
B[2][1][2][4] = + B[2][1][1][4] + B[2][2][1][4] = -858993406
B[2][1][3][1] = + A[2][1] + A[2][2] + A[2][3] = 21
B[2][1][3][2] = + B[2][1][3][1] + B[3][1][3][1] = -858993439
B[2][1][3][3] = + B[2][1][3][1] + B[3][1][3][1] + B[4][1][3][1] = -1717986899
B[2][1][3][4] = + B[2][1][1][4] + B[2][2][1][4] + B[2][3][1][4] = -1717986866
B[2][1][4][1] = + A[2][1] + A[2][2] + A[2][3] + A[2][4] = 30
B[2][1][4][2] = + B[2][1][4][1] + B[3][1][4][1] = -858993430
B[2][1][4][3] = + B[2][1][4][1] + B[3][1][4][1] + B[4][1][4][1] = -1717986890
B[2][1][4][4] = + B[2][1][4][1] + B[3][1][4][1] + B[4][1][4][1] + B[5][1][4][1] = 1717986946
B[2][1][5][1] = + A[2][1] + A[2][2] + A[2][3] + A[2][4] + A[2][5] = 40
B[2][1][5][2] = + B[2][1][5][1] + B[3][1][5][1] = -858993420
B[2][1][5][3] = + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] = -1717986880
B[2][1][5][4] = + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] + B[5][1][5][1] = 1717986956
B[2][2][1][1] = A[2][2] = 7
B[2][2][1][1] = + A[2][2] = 7
B[2][2][1][2] = + A[2][2] + A[3][2] = 19
B[2][2][1][3] = + A[2][2] + A[3][2] + A[4][2] = 36
B[2][2][1][4] = + A[2][2] + A[3][2] + A[4][2] + A[5][2] = 58
B[2][2][2][1] = + A[2][2] + A[2][3] = 15
B[2][2][2][2] = + B[2][2][2][1] + B[3][2][2][1] = -858993445
B[2][2][2][3] = + B[2][2][1][3] + B[2][3][1][3] = -858993424
B[2][2][2][4] = + B[2][2][1][4] + B[2][3][1][4] = -858993402
B[2][2][3][1] = + A[2][2] + A[2][3] + A[2][4] = 24
B[2][2][3][2] = + B[2][2][3][1] + B[3][2][3][1] = -858993436
B[2][2][3][3] = + B[2][2][3][1] + B[3][2][3][1] + B[4][2][3][1] = -1717986896
B[2][2][3][4] = + B[2][2][1][4] + B[2][3][1][4] + B[2][4][1][4] = -1717986862
B[2][2][4][1] = + A[2][2] + A[2][3] + A[2][4] + A[2][5] = 34
B[2][2][4][2] = + B[2][2][4][1] + B[3][2][4][1] = -858993426
B[2][2][4][3] = + B[2][2][4][1] + B[3][2][4][1] + B[4][2][4][1] = -1717986886
B[2][2][4][4] = + B[2][2][4][1] + B[3][2][4][1] + B[4][2][4][1] + B[5][2][4][1] = 1717986950
B[2][3][1][1] = A[2][3] = 8
B[2][3][1][1] = + A[2][3] = 8
B[2][3][1][2] = + A[2][3] + A[3][3] = 21
B[2][3][1][3] = + A[2][3] + A[3][3] + A[4][3] = 39
B[2][3][1][4] = + A[2][3] + A[3][3] + A[4][3] + A[5][3] = 62
B[2][3][2][1] = + A[2][3] + A[2][4] = 17
B[2][3][2][2] = + B[2][3][2][1] + B[3][3][2][1] = -858993443
B[2][3][2][3] = + B[2][3][1][3] + B[2][4][1][3] = -858993421
B[2][3][2][4] = + B[2][3][1][4] + B[2][4][1][4] = -858993398
B[2][3][3][1] = + A[2][3] + A[2][4] + A[2][5] = 27
B[2][3][3][2] = + B[2][3][3][1] + B[3][3][3][1] = -858993433
B[2][3][3][3] = + B[2][3][3][1] + B[3][3][3][1] + B[4][3][3][1] = -1717986893
B[2][3][3][4] = + B[2][3][1][4] + B[2][4][1][4] + B[2][5][1][4] = -1717986858
B[2][4][1][1] = A[2][4] = 9
B[2][4][1][1] = + A[2][4] = 9
B[2][4][1][2] = + A[2][4] + A[3][4] = 23
B[2][4][1][3] = + A[2][4] + A[3][4] + A[4][4] = 42
B[2][4][1][4] = + A[2][4] + A[3][4] + A[4][4] + A[5][4] = 66
B[2][4][2][1] = + A[2][4] + A[2][5] = 19
B[2][4][2][2] = + B[2][4][2][1] + B[3][4][2][1] = -858993441
B[2][4][2][3] = + B[2][4][1][3] + B[2][5][1][3] = -858993418
B[2][4][2][4] = + B[2][4][1][4] + B[2][5][1][4] = -858993394
B[2][5][1][1] = A[2][5] = 10
B[2][5][1][1] = + A[2][5] = 10
B[2][5][1][2] = + A[2][5] + A[3][5] = 25
B[2][5][1][3] = + A[2][5] + A[3][5] + A[4][5] = 45
B[2][5][1][4] = + A[2][5] + A[3][5] + A[4][5] + A[5][5] = 70
B[3][1][1][1] = A[3][1] = 11
B[3][1][1][1] = + A[3][1] = 11
B[3][1][1][2] = + A[3][1] + A[4][1] = 27
B[3][1][1][3] = + A[3][1] + A[4][1] + A[5][1] = 48
B[3][1][2][1] = + A[3][1] + A[3][2] = 23
B[3][1][2][2] = + B[3][1][2][1] + B[4][1][2][1] = -858993437
B[3][1][2][3] = + B[3][1][1][3] + B[3][2][1][3] = -858993412
B[3][1][3][1] = + A[3][1] + A[3][2] + A[3][3] = 36
B[3][1][3][2] = + B[3][1][3][1] + B[4][1][3][1] = -858993424
B[3][1][3][3] = + B[3][1][3][1] + B[4][1][3][1] + B[5][1][3][1] = -1717986884
B[3][1][4][1] = + A[3][1] + A[3][2] + A[3][3] + A[3][4] = 50
B[3][1][4][2] = + B[3][1][4][1] + B[4][1][4][1] = -858993410
B[3][1][4][3] = + B[3][1][4][1] + B[4][1][4][1] + B[5][1][4][1] = -1717986870
B[3][1][5][1] = + A[3][1] + A[3][2] + A[3][3] + A[3][4] + A[3][5] = 65
B[3][1][5][2] = + B[3][1][5][1] + B[4][1][5][1] = -858993395
B[3][1][5][3] = + B[3][1][5][1] + B[4][1][5][1] + B[5][1][5][1] = -1717986855
B[3][2][1][1] = A[3][2] = 12
B[3][2][1][1] = + A[3][2] = 12
B[3][2][1][2] = + A[3][2] + A[4][2] = 29
B[3][2][1][3] = + A[3][2] + A[4][2] + A[5][2] = 51
B[3][2][2][1] = + A[3][2] + A[3][3] = 25
B[3][2][2][2] = + B[3][2][2][1] + B[4][2][2][1] = -858993435
B[3][2][2][3] = + B[3][2][1][3] + B[3][3][1][3] = -858993409
B[3][2][3][1] = + A[3][2] + A[3][3] + A[3][4] = 39
B[3][2][3][2] = + B[3][2][3][1] + B[4][2][3][1] = -858993421
B[3][2][3][3] = + B[3][2][3][1] + B[4][2][3][1] + B[5][2][3][1] = -1717986881
B[3][2][4][1] = + A[3][2] + A[3][3] + A[3][4] + A[3][5] = 54
B[3][2][4][2] = + B[3][2][4][1] + B[4][2][4][1] = -858993406
B[3][2][4][3] = + B[3][2][4][1] + B[4][2][4][1] + B[5][2][4][1] = -1717986866
B[3][3][1][1] = A[3][3] = 13
B[3][3][1][1] = + A[3][3] = 13
B[3][3][1][2] = + A[3][3] + A[4][3] = 31
B[3][3][1][3] = + A[3][3] + A[4][3] + A[5][3] = 54
B[3][3][2][1] = + A[3][3] + A[3][4] = 27
B[3][3][2][2] = + B[3][3][2][1] + B[4][3][2][1] = -858993433
B[3][3][2][3] = + B[3][3][1][3] + B[3][4][1][3] = -858993406
B[3][3][3][1] = + A[3][3] + A[3][4] + A[3][5] = 42
B[3][3][3][2] = + B[3][3][3][1] + B[4][3][3][1] = -858993418
B[3][3][3][3] = + B[3][3][3][1] + B[4][3][3][1] + B[5][3][3][1] = -1717986878
B[3][4][1][1] = A[3][4] = 14
B[3][4][1][1] = + A[3][4] = 14
B[3][4][1][2] = + A[3][4] + A[4][4] = 33
B[3][4][1][3] = + A[3][4] + A[4][4] + A[5][4] = 57
B[3][4][2][1] = + A[3][4] + A[3][5] = 29
B[3][4][2][2] = + B[3][4][2][1] + B[4][4][2][1] = -858993431
B[3][4][2][3] = + B[3][4][1][3] + B[3][5][1][3] = -858993403
B[3][5][1][1] = A[3][5] = 15
B[3][5][1][1] = + A[3][5] = 15
B[3][5][1][2] = + A[3][5] + A[4][5] = 35
B[3][5][1][3] = + A[3][5] + A[4][5] + A[5][5] = 60
B[4][1][1][1] = A[4][1] = 16
B[4][1][1][1] = + A[4][1] = 16
B[4][1][1][2] = + A[4][1] + A[5][1] = 37
B[4][1][2][1] = + A[4][1] + A[4][2] = 33
B[4][1][2][2] = + B[4][1][2][1] + B[5][1][2][1] = -858993427
B[4][1][3][1] = + A[4][1] + A[4][2] + A[4][3] = 51
B[4][1][3][2] = + B[4][1][3][1] + B[5][1][3][1] = -858993409
B[4][1][4][1] = + A[4][1] + A[4][2] + A[4][3] + A[4][4] = 70
B[4][1][4][2] = + B[4][1][4][1] + B[5][1][4][1] = -858993390
B[4][1][5][1] = + A[4][1] + A[4][2] + A[4][3] + A[4][4] + A[4][5] = 90
B[4][1][5][2] = + B[4][1][5][1] + B[5][1][5][1] = -858993370
B[4][2][1][1] = A[4][2] = 17
B[4][2][1][1] = + A[4][2] = 17
B[4][2][1][2] = + A[4][2] + A[5][2] = 39
B[4][2][2][1] = + A[4][2] + A[4][3] = 35
B[4][2][2][2] = + B[4][2][2][1] + B[5][2][2][1] = -858993425
B[4][2][3][1] = + A[4][2] + A[4][3] + A[4][4] = 54
B[4][2][3][2] = + B[4][2][3][1] + B[5][2][3][1] = -858993406
B[4][2][4][1] = + A[4][2] + A[4][3] + A[4][4] + A[4][5] = 74
B[4][2][4][2] = + B[4][2][4][1] + B[5][2][4][1] = -858993386
B[4][3][1][1] = A[4][3] = 18
B[4][3][1][1] = + A[4][3] = 18
B[4][3][1][2] = + A[4][3] + A[5][3] = 41
B[4][3][2][1] = + A[4][3] + A[4][4] = 37
B[4][3][2][2] = + B[4][3][2][1] + B[5][3][2][1] = -858993423
B[4][3][3][1] = + A[4][3] + A[4][4] + A[4][5] = 57
B[4][3][3][2] = + B[4][3][3][1] + B[5][3][3][1] = -858993403
B[4][4][1][1] = A[4][4] = 19
B[4][4][1][1] = + A[4][4] = 19
B[4][4][1][2] = + A[4][4] + A[5][4] = 43
B[4][4][2][1] = + A[4][4] + A[4][5] = 39
B[4][4][2][2] = + B[4][4][2][1] + B[5][4][2][1] = -858993421
B[4][5][1][1] = A[4][5] = 20
B[4][5][1][1] = + A[4][5] = 20
B[4][5][1][2] = + A[4][5] + A[5][5] = 45
B[5][1][1][1] = A[5][1] = 21
B[5][1][1][1] = + A[5][1] = 21
B[5][1][2][1] = + A[5][1] + A[5][2] = 43
B[5][1][3][1] = + A[5][1] + A[5][2] + A[5][3] = 66
B[5][1][4][1] = + A[5][1] + A[5][2] + A[5][3] + A[5][4] = 90
B[5][1][5][1] = + A[5][1] + A[5][2] + A[5][3] + A[5][4] + A[5][5] = 115
B[5][2][1][1] = A[5][2] = 22
B[5][2][1][1] = + A[5][2] = 22
B[5][2][2][1] = + A[5][2] + A[5][3] = 45
B[5][2][3][1] = + A[5][2] + A[5][3] + A[5][4] = 69
B[5][2][4][1] = + A[5][2] + A[5][3] + A[5][4] + A[5][5] = 94
B[5][3][1][1] = A[5][3] = 23
B[5][3][1][1] = + A[5][3] = 23
B[5][3][2][1] = + A[5][3] + A[5][4] = 47
B[5][3][3][1] = + A[5][3] + A[5][4] + A[5][5] = 72
B[5][4][1][1] = A[5][4] = 24
B[5][4][1][1] = + A[5][4] = 24
B[5][4][2][1] = + A[5][4] + A[5][5] = 49
B[5][5][1][1] = A[5][5] = 25
B[5][5][1][1] = + A[5][5] = 25

Se observă ușor valori foarte mari în contrast cu cele din jur.

Se remarcă faptul că nu a trebuit să se initializeze matricea B cu 0 înainte de calcularea valorilor din ea, acest lucru fiind nefolositor.

Capturi de ecran 








Codul sursă


  1. #include <fstream>  
  2. #include <iostream>  
  3. using namespace std;  
  4.   
  5. const int maxn = 11,  
  6.     maxm = 11;  
  7.   
  8. // calculeaza suma pentru toate dreptunghiurile posibile  
  9. // care se pot lua in matricea A si apoi raspunde la o  
  10. // intrebare de tipul celei din enunt printr-o simpla  
  11. // accesare a unei valori din matricea-rezultat B.  
  12. int suma(int A[maxn][maxm],  
  13.     int B[maxn][maxm][maxm][maxn],  
  14.     int i, int j,  
  15.     int w, int h,  
  16.     int W, int H)  
  17. {  
  18.     // pt fiecare i de la care poate porni un dreptunghi..  
  19.     for (int k = 1; k <= H; ++k) // ca i  
  20.     {  
  21.         // pt fiecare j de la care poate porni un dreptunghi..  
  22.         for (int l = 1; l <= W; ++l) // ca j  
  23.         {  
  24.             B[k][l][1][1] = A[k][l];  
  25.   
  26.             // pt fiecare latime posibila a unui dreptunghi  
  27.             // care incepe de la punctul (i, j) curent adica  
  28.             // de la (k, l)..  
  29.             for (int m = 1; m <= W - l + 1; ++m) // ca w  
  30.             {  
  31.                 int val = 0;  
  32.                 for (int n = l + 1 - 1; n <= l + m - 1;  
  33.                     ++n) // n ca h  
  34.                 {  
  35.                     val += A[k][n];  
  36.                 }  
  37.                 B[k][l][m][1] = val;  
  38.   
  39.                 // pt fiecare inaltime posibila a unui dreptunghi  
  40.                 // care incepe de la punctul (i, j) curent adica  
  41.                 // de la (k, l)..  
  42.                 for (int n = 1; n <= H - k + 1; ++n) // ca h  
  43.                 {  
  44.                     // cazurile din acest if sunt calculate deja  
  45.                     if (n == 1 || (m == n && m == 1))  
  46.                     {  
  47.                         continue;  
  48.                     }  
  49.                       
  50.                     if (m == 1) // w  
  51.                     {  
  52.                         int val = 0;  
  53.                         for (int o = k + 1 - 1; o <= k + n - 1; // o ca i  
  54.                             ++o)  
  55.                         {  
  56.                             val += A[o][l];  
  57.                         }  
  58.                         B[k][l][1][n] = val;  
  59.                     }  
  60.                 }  
  61.             }  
  62.         }  
  63.     }  
  64.   
  65.     // pt fiecare i de la care poate porni un dreptunghi..  
  66.     for (int k = 1; k <= H; ++k) // ca i  
  67.     {  
  68.         // pt fiecare j de la care poate porni un dreptunghi..  
  69.         for (int l = 1; l <= W; ++l) // ca j  
  70.         {  
  71.             // pt fiecare latime posibila a unui dreptunghi  
  72.             // care incepe de la punctul (i, j) curent adica  
  73.             // de la (k, l)..  
  74.             for (int m = 1; m <= W - l + 1; ++m) // ca w  
  75.             {  
  76.                 // pt fiecare inaltime posibila a unui dreptunghi  
  77.                 // care incepe de la punctul (i, j) curent adica  
  78.                 // de la (k, l)..  
  79.                 for (int n = 1; n <= H - k + 1; ++n) // ca h  
  80.                 {  
  81.                     // cazurile din acest if sunt calculate deja  
  82.                     if (n == 1 || (m == n && m == 1))  
  83.                     {  
  84.                         continue;  
  85.                     }  
  86.   
  87.                     // inaltimea mai mica (sau egala) cu latimea,  
  88.                     // rezulta ca pt optimizare se insumeaza randuri  
  89.                     if (n <= m) // h <= w  
  90.                     {  
  91.                         int val = 0;  
  92.                         for (int p = k; p <= k + n - 1; ++p) // p ca i  
  93.                         {  
  94.                             val += B[p][l][m][1];  
  95.                         }  
  96.                         B[k][l][m][n] = val;  
  97.                     }  
  98.                     else // altfel se insumeaza coloane  
  99.                     {  
  100.                         int val = 0;  
  101.                         for (int p = l; p <= l + m - 1; ++p) // p ca j  
  102.                         {  
  103.                             val += B[k][p][1][n];  
  104.                         }  
  105.                         B[k][l][m][n] = val;  
  106.                     }  
  107.                 }  
  108.             }  
  109.         }  
  110.     }  
  111.   
  112.     return B[i][j][w][h];  
  113. }  
  114.   
  115. int test(int A[maxn][maxm],  
  116.     int B[maxn][maxm][maxm][maxn],  
  117.     int i, int j,  
  118.     int w, int h,  
  119.     int W, int H)  
  120. {  
  121.     cout << "Se calculeaza....." << endl << endl;  
  122.   
  123.     // pt fiecare i de la care poate porni un dreptunghi..  
  124.     for (int k = 1; k <= H; ++k) // ca i  
  125.     {  
  126.         // pt fiecare j de la care poate porni un dreptunghi..  
  127.         for (int l = 1; l <= W; ++l) // ca j  
  128.         {  
  129.             B[k][l][1][1] = A[k][l];  
  130.             cout << "B[" << k << "][" << l << "]" <<  
  131.                 "[" << 1 << "][" << 1 << "] = A[" <<  
  132.                 k << "][" << l << "] = " <<  
  133.                 B[k][l][1][1] << endl;  
  134.   
  135.             // pt fiecare latime posibila a unui dreptunghi  
  136.             // care incepe de la punctul (i, j) curent adica  
  137.             // de la (k, l)..  
  138.             for (int m = 1; m <= W - l + 1; ++m) // ca w  
  139.             {  
  140.                 // (n == 1) // n ca h  
  141.                 cout << "B[" << k << "][" << l << "]" <<  
  142.                     "[" << m << "][" << 1 << "] =";  
  143.                 int val = 0;  
  144.                 for (int n = l + 1 - 1; n <= l + m - 1;  
  145.                     ++n) // n ca h  
  146.                 {  
  147.                     cout << " + A[" << k << "][" << n << "]";  
  148.                     val += A[k][n];  
  149.                 }  
  150.                 B[k][l][m][1] = val;  
  151.                 cout << " = " <<  
  152.                     B[k][l][m][1] << endl;  
  153.   
  154.                 // pt fiecare inaltime posibila a unui dreptunghi  
  155.                 // care incepe de la punctul (i, j) curent adica  
  156.                 // de la (k, l)..  
  157.                 for (int n = 1; n <= H - k + 1; ++n) // ca h  
  158.                 {  
  159.                     // cazurile din acest if sunt calculate deja  
  160.                     if (n == 1 || (m == n && m == 1))  
  161.                     {  
  162.                         continue;  
  163.                     }  
  164.   
  165.                     if (m == 1) // w  
  166.                     {  
  167.                         cout << "B[" << k << "][" << l << "]" <<  
  168.                             "[" << 1 << "][" << n << "] =";  
  169.                         int val = 0;  
  170.                         for (int o = k + 1 - 1; // o ca i  
  171.                             o <= k + n - 1;  
  172.                             ++o)  
  173.                         {  
  174.                             cout << " + A[" << o << "][" << l << "]";  
  175.                             val += A[o][l];  
  176.                         }  
  177.                         B[k][l][1][n] = val;  
  178.                         cout << " = " << B[k][l][1][n] << endl;  
  179.                         continue;  
  180.                     }  
  181.   
  182.                     // inaltimea mai mica (sau egala) cu latimea,  
  183.                     // rezulta ca pt optimizare se insumeaza randuri  
  184.                     if (n <= m) // h <= w  
  185.                     {  
  186.                         cout << "B[" << k << "][" << l << "]" <<  
  187.                             "[" << m << "][" << n << "] =";  
  188.                         int val = 0;  
  189.                         for (int p = k; p <= k + n - 1; ++p) // p ca i  
  190.                         {  
  191.                             cout << " + B[" << p << "][" << l << "][" <<  
  192.                                 m << "][" << 1 << "]";  
  193.                             val += B[p][l][m][1];  
  194.                         }  
  195.                         B[k][l][m][n] = val;  
  196.                         cout << " = " <<  
  197.                             B[k][l][m][n] << endl;  
  198.                     }  
  199.                     else // altfel se insumeaza coloane  
  200.                     {  
  201.                         cout << "B[" << k << "][" << l << "]" <<  
  202.                             "[" << m << "][" << n << "] =";  
  203.                         int val = 0;  
  204.                         for (int p = l; p <= l + m - 1; ++p) // p ca j  
  205.                         {  
  206.                             cout << " + B[" << k << "][" << p << "][" <<  
  207.                                 1 << "][" << n << "]";  
  208.                             val += B[k][p][1][n];  
  209.                         }  
  210.                         B[k][l][m][n] = val;  
  211.                         cout << " = " <<  
  212.                             B[k][l][m][n] << endl;  
  213.                     }  
  214.                 }  
  215.             }  
  216.         }  
  217.     }  
  218.   
  219.     return B[i][j][w][h];  
  220. }  
  221.   
  222. int main()  
  223. {  
  224.     int A[maxn][maxm],  
  225.         B[maxn][maxm][maxm][maxn],  
  226.         H, W, y, x, w, h;  
  227.   
  228.     ifstream in("suma.in");  
  229.     in >> W >> H >> x >> y >> w >> h;  
  230.     for (int i = 1; i <= H; ++i)  
  231.     {  
  232.         for (int j = 1; j <= W; ++j)  
  233.         {  
  234.             in >> A[i][j];  
  235.         }  
  236.     }  
  237.     in.close();  
  238.   
  239.     ofstream out("suma.out");  
  240.     out << suma(A, B, y, x, w, h, W, H) <<  
  241.         endl << endl;  
  242.   
  243.     out << "Dreptunghiuri de la  X = " << x <<  
  244.         ", Y = " << y << ":" << endl;  
  245.     for (int m = 1; m <= W - x + 1; ++m) // ca w  
  246.     {  
  247.         for (int n = 1; n <= H - y + 1; ++n) // ca h  
  248.         {  
  249.             out << "B[" << y << "][" << x << "][" << m << "][" <<  
  250.                 n << "] = " << B[y][x][m][n] << '\t';  
  251.         }  
  252.         out << endl;  
  253.     }  
  254.   
  255.     out.close();  
  256.   
  257.     return 0;  
  258. }
la
Etichete: , , , ,

Niciun comentariu:

Trimiteți un comentariu

Abonați-vă la: Postare comentarii (Atom)