Simulări pe matrice — sistemul trăiește într-o grilă

De ce contează?

Un foc pornește într-un colț al unei păduri desenate ca o grilă. La fiecare minut, focul se întinde la căsuțele vecine. Vrei să simulezi cum arată pădurea după câteva minute. Sistemul trăiește într-o matrice, iar regula se aplică tuturor celulelor deodată.

Când folosești o matrice

Reprezinți sistemul printr-o matrice când obiectele stau pe o grilă 2D: fiecare celulă are două coordonate (linie și coloană). Hărți, table de joc, terenuri, ecrane de pixeli.

Ideile de la simulările pe vectori se transferă direct, doar că lucrezi cu doi indici și (de obicei) patru vecini.

Observația-cheie

Aceeași capcană ca la vectori, amplificată: dacă noua valoare a unei celule depinde de vecini, actualizarea pe loc propagă efectul în același pas. Folosește o a doua matrice next.

Exemplu: propagarea focului

1 = arde, 0 = pădure. La fiecare pas, orice celulă vecină (sus/jos/stânga/dreapta) cu una care arde se aprinde. Stare inițială: arde doar (1,1).

Curent: arde doar (1,1)

După un pas, focul cuprinde și vecinii direcți:

Next: (1,1) a aprins vecinii (0,1),(2,1),(1,0),(1,2)

Implementare C++

#include <iostream>
using namespace std;

int cur[100][100], nxt[100][100];
int dx[] = {-1, 1, 0, 0}; // cei 4 vecini
int dy[] = {0, 0, -1, 1};

int main() {
    int n, m, pasi;
    cin >> n >> m >> pasi;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> cur[i][j];

    for (int t = 0; t < pasi; t++) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                nxt[i][j] = cur[i][j]; // ce arde ramane aprins
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m) // in grila?
                        if (cur[ni][nj] == 1) nxt[i][j] = 1; // vecin care arde
                }
            }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cur[i][j] = nxt[i][j]; // trecem la noua stare
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cout << cur[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Citim din cur, scriem în nxt, apoi copiem — toate celulele văd aceeași stare veche.

Complexitate

Aspect	Cost
Un pas de simulare	O(n·m)
`pasi` pași	O(pasi · n · m)
Memorie	O(n·m) (două matrice)

Greșeli frecvente

Greșeli frecvente de concurs:

Actualizare pe loc în cascadă. Fără matricea next, focul aprins acum poate aprinde alți vecini în același pas — propagare prea rapidă. Folosește nxt.
Vecin în afara grilei. La margini, (ni, nj) poate ieși din matrice. Verifică 0 ≤ ni < n și 0 ≤ nj < m înainte de acces.
Uiți să copiezi nxt în cur. Fără pasul de trecere, simularea rămâne în starea inițială la fiecare iterație.
Confunzi 4 vecini cu 8. Dacă regula include diagonalele, ai nevoie de liste dx/dy cu 8 perechi, nu 4.

Recapitulare

Folosești o matrice când sistemul e o grilă 2D (linie + coloană pentru fiecare celulă).
Pentru reguli bazate pe vecini, calculează în nxt din cur, apoi interschimbă — actualizare simultană.
Parcurge vecinii cu vectori de direcție + verificare de margine; cost O(pasi · n · m).