Simulări în matrice

De ce contează?

Imaginează-ți o hartă în care focul se extinde: la fiecare minut, orice celulă lângă foc ia foc și ea. Ca să prezici cum arată harta peste 5 minute, „rulezi" regula minut cu minut. O simulare pe matrice e exact asta: aplici o regulă locală, pas cu pas, pe toată grila.

Ce este o simulare pe matrice

O simulare reproduce un proces pas cu pas pe o grilă. La fiecare pas, fiecare celulă se actualizează după o regulă care depinde de starea curentă (adesea de vecinii ei). Repeți pașii până la o condiție de oprire.

Cei patru (sau opt) vecini

O celulă (i, j) are vecini pe direcțiile sus/jos/stânga/dreapta. Îi exprimi cu doi vectori de direcție:

int di[] = {-1, 1, 0, 0};   // sus, jos, -, -
int dj[] = {0, 0, -1, 1};   // -, -, stanga, dreapta
// vecinul k: (i + di[k], j + dj[k])

Capcana centrală: actualizare pe loc vs auxiliară

Dacă noua valoare a unei celule depinde de vecini, nu scrie direct în matrice — ai strica starea pentru celulele următoare. Folosește o matrice auxiliară nou:

#include <iostream>
using namespace std;

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

    int di[] = {-1, 1, 0, 0};
    int dj[] = {0, 0, -1, 1};

    // un pas: fiecare celula devine suma vecinilor valizi
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int s = 0;
            for (int k = 0; k < 4; k++) {
                int ni = i + di[k], nj = j + dj[k];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                    s += a[ni][nj];     // citim starea VECHE
                }
            }
            nou[i][j] = s;              // scriem in matricea auxiliara
        }
    }

    // copiem starea noua peste cea veche
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            a[i][j] = nou[i][j];
    return 0;
}

Observația-cheie

Toate celulele citesc din a (starea veche) și scriu în nou. Abia după ce ai calculat toată noua stare, o copiezi înapoi. Modificând pe loc, vecinii deja actualizați ar „contamina" calculul — un bug subtil și frecvent.

Verificarea marginilor

Înainte de a accesa un vecin, verifici că indicii lui sunt valizi:

ni >= 0 && ni < m && nj >= 0 && nj < n

Pe colțuri și margini, unele direcții ies din matrice — condiția le sare.

Complexitate

Operație	Timp	Spațiu
un pas	O(m·n)	O(m·n) pentru auxiliară
P pași	O(P·m·n)	O(m·n)

Greșeli frecvente

Capcane reale la simulări pe matrice:

Actualizare pe loc: scrii noua valoare în a și vecinii următori citesc starea greșită. Folosește o matrice auxiliară.
Acces în afara matricei: uiți să verifici marginile și citești a[-1][j] sau a[m][j]. Verifică indicii vecinului.
Uiți să copiezi nou în a: simulezi un pas dar nu actualizezi starea → toate generațiile sunt identice.
Vectori de direcție nealineați: di și dj trebuie să descrie aceeași direcție pe același index k. Dezaliniați, sari în diagonală fără să vrei.

De reținut

Simulare = aplici o regulă locală pe toată grila, pas cu pas, până la o condiție de oprire.
Citește starea veche, scrie în matricea auxiliară, apoi copiaz-o înapoi (nu pe loc).
Verifică marginile înainte de a accesa un vecin; un pas e O(m·n).