Clasa a 7-a lecția 5 - 15 oct 2015

From Algopedia
Jump to navigationJump to search

Temă Rezolvări

Rezolvări aici [1]

Temă

Rezolvări aici [2]

Lecție

Recursivitate - încheiere

Fill recursiv (flood fill)

Introducere

Algoritmul fill "umple" toate golurile accesibile de la un punct dat. Golurile pot fi elemente zero intr-o matrice, de exemplu, iar vecinii pot fi definiți ca elementele adiacente pe linie și coloană (acesta este cazul cel mai întîlnit). Alteori vecinii pot fi definiți ca avînd un punct comun cu elementul curent, ceea ce include și elementele alăturate pe diagonală. Să luăm un exemplu clasic:

Se dă o matrice a[m][n] cu elemente 0 și 1, 0 semnificînd liber și 1 semnificînd zid, precum și o poziție în matrice, (l, c). Să se spuna cîte elemente 0 sînt accesibile de la (l, c) avansînd doar pe linie sau pe coloană. 

int suma;
...
void fill( int l, int c ) {
  suma++;
  a[l][c] = 1;
  if ( l > 0 && a[l-1][c] == 0 )
    fill( l - 1, c );
  if ( l < m-1 && a[l+1][c] == 0  )
    fill( l + 1, c );
  if ( c > 0 && a[l][c-1] == 0  )
    fill( l, c - 1 );
  if ( c < n-1 && a[l][c+1] == 0  )
    fill( l, c + 1 );
}
...
int main() {
  ...
  suma = 0;
  if ( a[l][c] == 0 )
    fill( l, c );
  printf( "%d", suma );
  ...
}

Acest algoritm are complexitate O(m×n) ca timp, deoarece poate parcurge toate elementele matricei, iar prelucrarea per element este O(1). Memoria ocupată este de asemenea O(m×n) deoarece fiecare apel recursiv necesită O(1) memorie și putem avea O(m×n) apeluri recursive unul în altul.

Atenție! Acesta este principalul impediment al metodei! Ea folosește foarte multă memorie suplimentară.

Optimizări

Bordare matrice

O primă optimizare de timp este clasică. Pentru a face programul atît mai rapid cît și mai scurt putem borda matricea de jur împrejur cu elementul zid, în cazul nostru 1. Astfel vom scuti testul de ieșire a coordonatelor din matrice. Funcția se simplifică: 

void fill( int l, int c ) {
  suma++;
  a[l][c] = 1;
  if ( a[l-1][c] == 0 )
    fill( l - 1, c );
  if ( a[l+1][c] == 0  )
    fill( l + 1, c );
  if ( a[l][c-1] == 0  )
    fill( l, c - 1 );
  if ( a[l][c+1] == 0  )
    fill( l, c + 1 );
}
Reducere memorie folosită

Cum calculăm memoria ocupată? Țineți minte: fiecare apel recursiv ocupă memorie echivalentul unui int. Pe un calculator de 32 de biți, cum sint cele pe care lucrăm noi, aceasta înseamnă patru octeți. Aceasta este adresa de întoarcere din funcție. Alte elemente care ocupă memorie pe stivă sînt parametrii transmiși și variabilele declarate în funcție. În cazul nostru vom avea 8 octeți cei doi parametri.

Dacă micșorarea memoriei folosite este esențială putem elimina acești parametri, făcînd variabilele l și c globale, astfel: 

int l, c;
...
void fill() {
  suma++;
  a[l][c] = 1;
  l--;
  if ( a[l][c] == 0 )
    fill();
  l++;
  l++;
  if ( a[l][c] == 0  )
    fill();
  l--;
  c--;
  if ( a[l][c] == 0  )
    fill();
  c++;
  c++;
  if ( a[l][c] == 0  )
    fill();
  c--;
}

Este o modificare urîtă, care face codul nelizibil, dar uneori necesară la olimpiadă. Nu uitați că chiar și în această formă algoritmul va folosi 4 octeți pe apel recursiv imbricat pentru adresa de revenire din funcție.

Aplicații

Se considera o harta pătratică în care insulele sunt simbolizate cu 1 si apele cu 0. Colorați diferit fiecare insulă din această hartă (prima insulă va fi marcată cu 2, a doua cu 3, etc...). Afișați numărul de insule găsite. 

#include <stdio.h>
#include <assert.h>

#define MAX_N 100
#define MAX_M 100

int mat[1 + MAX_N + 1][1 + MAX_M + 1];

void fill(int l, int c, int vechi, int nou) {
	assert(mat[l][c] == vechi);
	// sunt sigur ca celula curenta are valoarea 1
	mat[l][c] = nou;
	if (mat[l+1][c] == vechi) // jos
		fill(l+1, c, vechi, nou);
	if (mat[l][c+1] == vechi) // dreapta
		fill(l, c+1, vechi, nou);
	if (mat[l-1][c] == vechi) // sus
		fill(l-1, c, vechi, nou);
	if (mat[l][c-1] == vechi) // stanga
		fill(l, c-1, vechi, nou);
}

int main(void) {
	int N, M;
	int i, j;

	// citirea datelor
	scanf("%d", &N, &M);
	for (i = 1; i <= N; ++i) {
		for (j = 1; j <= M; ++j) {
			scanf("%d", &mat[i][j]);
		}
	}

	// calcularea solutiei
	int nrInsule = 0;
	for (i = 1; i <= N; ++i) {
		for (j = 1; j <= M; ++j) {
			if (mat[i][j] == 1) {
				fill(i, j, 1, nrInsule + 2);
				nrInsule++;
			}
		}
	}

	// afisarea solutiei
	printf("%d\n", nrInsule);
	return 0;
}

Ca și complexitate, vom avea complexitate O( n * m ) timp, O( n * m ) memorie

Aplicații

  • Găsire ieșire din labirint: găsirea unui punct (sau tuturor punctelor) de ieșire dintr-un labirint, dacă există.
  • Calcul suprafață goluri: acesta este exemplul de mai sus, care numără elementele zero accesibile din punctul inițial.
  • Calcul număr de goluri: denumite și componente conexe, putem folosi fill pentru a număra cîte goluri disjuncte există (astfel încît să nu se poată ajunge de la un gol la altul). Pentru aceasta vom parcurge matricea în orice ordine și vom porni cîte un fill din fiecare loc unde găsim un element 0.

Concluzie

Fill este o unealtă simplă și utilă, ușor de folosit la concursuri. Principalul ei neajuns este memoria ocupată. Ce facem în situația cînd matricea este prea mare și memoria disponibilă insuficientă pentru a folosi flood fill? În această situație putem folosi BFS fill (breadth first search), care, atunci cînd este aplicat pe o matrice se mai numește și algoritmul Lee. El folosește o coadă pentru a menține frontiera deja acoperită, reducînd memoria la O(m+n).

BFS ( Algoritmul lui Lee )

#include <stdio.h>
#include <assert.h>

#define MAX_N 100
#define MAX_M 100

int mat[1 + MAX_N + 1][1 + MAX_M + 1];
int dist[1 + MAX_N + 1][1 + MAX_M + 1];

int dirLin[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirCol[] = { 0,  1, 1, 1, 0,-1,-1, -1};

int linie[MAX_N * MAX_M];
int coloana[MAX_N * MAX_M];
int inceput, sfarsit;

void fill(int l, int c, int vechi, int nou) {
  assert(mat[l][c] == vechi);
  // sunt sigur ca celula curenta are valoarea 1
  mat[l][c] = nou;
  int i;
  for (i = 0; i < 8; ++i) {
    if (mat[l + dirLin[i]][c + dirCol[i]] == vechi)
      fill(l + dirLin[i], c + dirCol[i], vechi, nou);
  }
}

int main(void) {
  int N, M;
  int i, j;

  // citirea datelor
  scanf("%d %d", &N, &M);
  for (i = 1; i <= N; ++i) {
    for (j = 1; j <= M; ++j) {
      scanf("%d", &mat[i][j]);
    }
  }
  int L, C;
  scanf("%d %d", &L, &C);

  // calcularea solutiei
  for (i = 0; i <= N + 1; ++i) {
    for (j = 0; j <= M + 1; ++j) {
      dist[i][j] = -1;
    }
  }
  dist[L][C] = 0;
  int l, c;
  int vechi = 0;
  inceput = sfarsit = 0;
  linie[sfarsit] = L;
  coloana[sfarsit] = C;
  sfarsit++;
  while (inceput < sfarsit) {
    l = linie[inceput];
    c = coloana[inceput];
    inceput++;
    for (i = 0; i < 8; ++i) {
      if (mat[l + dirLin[i]][c + dirCol[i]] == 1 && dist[l + dirLin[i]][c + dirCol[i]] == -1) {
	dist[l + dirLin[i]][c + dirCol[i]] = dist[l][c] + 1;
	linie[sfarsit] = l + dirLin[i];
	coloana[sfarsit] = c + dirCol[i];
	sfarsit++;
      }
    }
    ++vechi;
  }

  // afisarea solutiei
  for (i = 0; i <= N + 1; ++i) {
    for (j = 0; j <= M + 1; ++j) {
      if (dist[i][j] == -1) {
	printf("  ");
      }   
      else {
	printf("%1d ", dist[i][j]);
      }
    }
  printf("\n");
  }
  return 0;
}
/*

6 8
0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0
0 1 0 1 1 1 0 0
0 1 1 1 1 0 0 0
0 0 1 0 1 1 0 0
0 0 0 0 0 0 0 0
3 4
 */


Temă

Tema 5 clasa a 7-a

  • oras ca aplicație de flood fill
  • alee ca aplicație de BFS

Rezolvări aici [3]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_7-a_lecția_5_-_15_oct_2015&oldid=13490"