Programare Competitivă

Fill și algoritmul lui Lee (BFS pe matrice)

Multe probleme cer să explorăm o matrice pornind dintr-un punct: să umplem o zonă, să găsim drumul cel mai scurt într-un labirint, sau să numărăm regiunile conexe. Pentru asta folosim două tehnici fundamentale: Fill (umplere) și algoritmul lui Lee (BFS pe grilă).

Ambele se bazează pe structura de coadă (Queue - FIFO): adăugăm celulele descoperite la spate și le procesăm de la față. Aceasta garantează explorarea nivel cu nivel (cele mai apropiate celule sunt procesate primele). Varianta cu stivă (LIFO) ar produce DFS - explorare în adâncime, nu în lățime.

Flood Fill

Flood Fill umple o zonă conectată cu o valoare nouă - ca și cum ai turna vopsea dintr-un punct și ea se extinde în toate direcțiile posibile.

Problema

Avem o matrice cu 0 și 1. Pornind de la o poziție (sx, sy) care conține 0, vrem să “umplem” toată zona de 0-uri conectată (sus, jos, stânga, dreapta) cu valoarea 2.

Înainte:                  După fill din (2,2):
1 1 1 0 0                1 1 1 2 2
1 0 0 0 1                1 2 2 2 1
1 0 1 0 1       →        1 2 1 2 1
0 0 1 1 1                2 2 1 1 1
1 1 1 1 1                1 1 1 1 1

Implementare cu coadă (BFS)

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[101][101];
int n, m;

// Direcțiile: sus, jos, stânga, dreapta
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// Coadă simplă
int qx[10001], qy[10001];

void fill(int sx, int sy, int culoare) {
    int st = 0, dr = 0;
    qx[dr] = sx;
    qy[dr] = sy;
    dr++;
    a[sx][sy] = culoare;

    while (st < dr) {
        int x = qx[st];
        int y = qy[st];
        st++;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0) {
                a[nx][ny] = culoare;
                qx[dr] = nx;
                qy[dr] = ny;
                dr++;
            }
        }
    }
}

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

    int sx, sy;
    fin >> sx >> sy;

    fill(sx, sy, 2);

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

    return 0;
}

Vectorii de direcție

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

Aceștia codifică cele 4 direcții:

Direcție dx dy
Sus -1 0
Jos +1 0
Stânga 0 -1
Dreapta 0 +1

Vecinul (nx, ny) = (x + dx[d], y + dy[d]) pentru fiecare direcție d.

8 direcții: dacă problema cere și diagonale, adăugăm: dx[] = {-1,-1,-1,0,0,1,1,1}, dy[] = {-1,0,1,-1,1,-1,0,1}.

Numărarea componentelor conexe

O componentă conexă este o regiune de celule cu aceeași valoare, conectate între ele.

Problema

Câte “insule” de 1 sunt în matrice?

0 0 1 0 0
0 1 1 0 0        → 3 insule
0 0 0 1 1
1 1 0 0 1

Ideea

Parcurgem matricea. Când găsim un 1 nevizitat, pornim un fill care marchează toată insula. Numărăm câte fill-uri am făcut.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[101][101];
int n, m;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int qx[10001], qy[10001];

void fill(int sx, int sy) {
    int st = 0, dr = 0;
    qx[dr] = sx; qy[dr] = sy; dr++;
    a[sx][sy] = 0;

    while (st < dr) {
        int x = qx[st], y = qy[st]; st++;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 1) {
                a[nx][ny] = 0;
                qx[dr] = nx; qy[dr] = ny; dr++;
            }
        }
    }
}

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

    int insule = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 1) {
                insule++;
                fill(i, j);
            }

    fout << insule;

    return 0;
}

date.in:

4 5
0 0 1 0 0
0 1 1 0 0
0 0 0 1 1
1 1 0 0 1

date.out:

3

Algoritmul lui Lee - distanța minimă

Algoritmul lui Lee este BFS pe matrice. Găsește distanța minimă (în număr de pași) de la un punct de start la toate celelalte celule accesibile.

Problema: labirint

Avem o matrice cu 0 (liber) și 1 (zid). Pornim de la (sx, sy) și vrem distanța minimă până la (fx, fy).

Labirint:
0 0 1 0 0
1 0 1 0 1
0 0 0 0 1
0 1 1 0 0

Start: (1,1), Final: (4,5)

Ideea

BFS explorează celulele nivel cu nivel - mai întâi cele la distanță 1, apoi la distanță 2, etc. Prima dată când ajungem la o celulă, avem distanța minimă.

Folosim o matrice dist[i][j] care reține distanța de la start. Inițial -1 (nevizitat).

Codul complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[101][101];
int dist[101][101];
int n, m;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int qx[10001], qy[10001];

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            fin >> a[i][j];
            dist[i][j] = -1;
        }

    int sx, sy, fx, fy;
    fin >> sx >> sy >> fx >> fy;

    // BFS (Lee)
    int st = 0, dr = 0;
    qx[dr] = sx; qy[dr] = sy; dr++;
    dist[sx][sy] = 0;

    while (st < dr) {
        int x = qx[st], y = qy[st]; st++;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m
                && a[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                qx[dr] = nx; qy[dr] = ny; dr++;
            }
        }
    }

    fout << dist[fx][fy];

    return 0;
}

date.in:

4 5
0 0 1 0 0
1 0 1 0 1
0 0 0 0 1
0 1 1 0 0
1 1
4 5

date.out:

8

Pas cu pas

Distanțe calculate (Lee):
 0  1  .  .  .
 .  2  .  .  .
 4  3  4  5  .
 5  .  .  6  7  → dist[4][5] = 8?

De fapt, drumul: (1,1)→(1,2)→(2,2)→(3,2)→(3,3)→(3,4)→(4,4)→(4,5) = 7 pași. Verificarea exactă depinde de labirint.

Matricea distanțelor

Lee calculează distanța de la start la toate celulele, nu doar la final. Putem afișa toată matricea distanțelor:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (dist[i][j] == -1)
            fout << "# ";
        else
            fout << dist[i][j] << " ";
    }
    fout << "\n";
}

# = inaccesibil (zid sau celulă la care nu se poate ajunge).

Lee cu mai multe surse

Dacă avem mai multe puncte de start, le punem pe toate în coadă la început:

// Toate celulele cu valoarea 2 sunt surse
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] == 2) {
            dist[i][j] = 0;
            qx[dr] = i; qy[dr] = j; dr++;
        }

// BFS normal de aici
while (st < dr) {
    // ...
}

Rezultatul: dist[i][j] = distanța minimă de la (i,j) la cea mai apropiată sursă.

Structura generală BFS pe matrice

1. Inițializăm dist cu -1 (nevizitat)
2. Punem start-ul în coadă, dist[sx][sy] = 0
3. Cât timp coada nu e goală:
   a. Scoatem (x, y) din coadă
   b. Pentru fiecare vecin (nx, ny):
      - Verificăm limite, ziduri, vizitat
      - dist[nx][ny] = dist[x][y] + 1
      - Adăugăm în coadă

Fill vs Lee

Flood Fill Lee (BFS)
Ce face Umple o regiune Calculează distanțe
Rezultat Marchează celulele Matrice de distanțe
Complexitate O(n*m) O(n*m)
Folosim pentru Componente conexe, umplere Drum minim, distanțe

Ambele sunt BFS pe matrice. Diferența e ce reținem: fill marchează, Lee calculează distanțe.

Greșeli frecvente

1. Coada prea mică

Coada trebuie să poată conține cel mult n * m elemente (dacă toate celulele sunt accesibile).

int qx[100001], qy[100001]; // pentru n,m <= 316

2. Nu verificăm limitele

if (nx >= 1 && nx <= n && ny >= 1 && ny <= m // OBLIGATORIU
    && a[nx][ny] == 0 && dist[nx][ny] == -1)

Fără verificarea limitelor, accesăm memorie în afara matricei.

3. Marcăm celula prea târziu

// GREȘIT - o adăugăm în coadă dar nu o marcăm imediat
qx[dr] = nx; qy[dr] = ny; dr++;
// ... alt vecin o adaugă din nou!

// CORECT - marcăm ÎNAINTE de a adăuga în coadă
dist[nx][ny] = dist[x][y] + 1; // marcăm
qx[dr] = nx; qy[dr] = ny; dr++;

4. Confuzia fill recursiv cu BFS

Fill-ul se poate implementa și recursiv (DFS), dar pe matrici mari dă stack overflow. BFS cu coadă e mereu sigur.

Ce să reții

  • Flood Fill: umple o zonă conectată pornind dintr-un punct.
  • Lee (BFS): calculează distanța minimă de la start la toate celulele.
  • Ambele folosesc o coadă și vectorii de direcție dx, dy.
  • Verificăm mereu: limite, ziduri, vizitat.
  • Marcăm celula înainte de a o adăuga în coadă.
  • Complexitate: O(n*m) - fiecare celulă e vizitată o singură dată.
  • Coada trebuie dimensionată la n * m.

Probleme

pbinfoLabirint3→

pbinfoMewtwo→

pbinfoRj→

pbinfoSudest→

pbinfoInsule→

pbinfoSchior→

Cuprins Inapoi Inainte