Tablouri bidimensionale

Declararea unei matrice, cei doi indici, citirea pe linii și parcurgerile de bază.

Ce este

Un tablou bidimensional, adică o matrice, are două dimensiuni: linii și coloane. Un element se identifică prin doi indici.

int a[101][101];

a[i][j] este elementul de pe linia i, coloana j. Ordinea aceasta e aceeași peste tot, iar inversarea ei e o sursă constantă de confuzie.

Ca și la vectori, dimensiunile trebuie să fie constante la compilare, iar pentru matrice mari e de preferat declararea în afara lui main. O matrice 1000 × 1000 de întregi ocupă vreo 4 MB, mult pentru zona de memorie a unei funcții.

Citirea

int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        cin >> a[i][j];

Bucla exterioară merge pe linii, cea interioară pe coloane. Așa datele se citesc în ordinea firească: linie cu linie, de la stânga la dreapta.

Pentru o matrice pătratică se citește un singur n, iar ambele bucle merg până la el.

Afișarea

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++)
        cout << a[i][j] << " ";
    cout << "\n";
}

cout << "\n" stă între cele două bucle, deci se execută după fiecare linie completă, nu după fiecare element. Aici se greșește cel mai des la afișarea matricelor.

Parcurgeri

Pe linii

Cum am văzut mai sus. Prelucrarea unei singure linii i:

long long suma = 0;
for (int j = 1; j <= m; j++)
    suma += a[i][j];

Pe coloane

Se inversează ordinea buclelor: fixezi coloana, parcurgi liniile.

for (int j = 1; j <= m; j++) {
    long long suma = 0;
    for (int i = 1; i <= n; i++)
        suma += a[i][j];
    cout << "coloana " << j << ": " << suma << "\n";
}

Observă unde se inițializează suma: în interiorul buclei exterioare, pentru că fiecare coloană are propria sumă. Dacă ar fi în afară, ai aduna toate coloanele la un loc. La fel procedezi pentru maximul fiecărei linii, numărul de elemente pare de pe fiecare coloană și așa mai departe.

Diagonalele unei matrice pătratice

Diagonala principală merge din colțul stânga-sus în dreapta-jos. Elementele ei au i == j.

Diagonala secundară merge din dreapta-sus în stânga-jos. Elementele ei au i + j == n + 1 (cu indexare de la 1) sau i + j == n - 1 (de la 0).

long long dp = 0, ds = 0;
for (int i = 1; i <= n; i++) {
    dp += a[i][i];
    ds += a[i][n + 1 - i];
}

O singură buclă pentru amândouă. Nu ai nevoie de doi indici, pentru că al doilea se calculează din primul.

Cele două condiții împart matricea în patru zone triunghiulare:

Combinându-le, obții triunghiurile de nord, sud, est și vest, care apar des în enunțuri. Zona de nord, de exemplu, este i < j && i + j < n + 1.

Vecinii unui element

Multe probleme cer să te uiți în jurul unei poziții: a[i-1][j], a[i+1][j], a[i][j-1], a[i][j+1].

Pericolul e la margine. Pe prima linie, a[i-1][j] este în afara matricei.

Ai două soluții. Testezi de fiecare dată:

if (i > 1 && a[i-1][j] > a[i][j]) ...

Sau lași o ramă goală: dacă lucrezi cu indici de la 1 și matricea e declarată global (în afara funcțiilor) și mai mare decât n, liniile 0 și n+1 există și conțin zero. Uneori asta rezolvă problema fără niciun test, dar numai dacă zero este o valoare neutră pentru ce calculezi.

Un exemplu complet

Se citește o matrice cu n linii și m coloane. Să se afișeze indicele liniei cu suma elementelor maximă.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    int linia = 1;
    long long maxim = 0;
    for (int j = 1; j <= m; j++)
        maxim += a[1][j];

    for (int i = 2; i <= n; i++) {
        long long s = 0;
        for (int j = 1; j <= m; j++)
            s += a[i][j];
        if (s > maxim) {
            maxim = s;
            linia = i;
        }
    }

    cout << linia;
    return 0;
}

Suma primei linii se calculează separat, ca valoare de pornire. E aceeași idee ca la maximul dintr-un vector, unde inițializezi cu primul element, nu cu zero.

De reținut

• a[i][j] este linia i, coloana j. Nu inversa.
• Parcurgerea pe coloane inversează ordinea buclelor.
• Ce se calculează per linie se inițializează în interiorul buclei exterioare.
• Diagonala principală: i == j. Cea secundară: i + j == n + 1.
• La vecini, testează marginile înainte să citești.