10 2018 Lectia21
Temă Rezolvări
Rezolvări aici [1]
Temă
Rezolvări aici [2]
Lecție
Recursivitate - FILL
Fill recursiv (flood fill)
Introducere
Algoritmul fill "umple" toate golurile accesibile de la un punct dat. Golurile pot fi elemente diferite de 0 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 zid și 1 semnificînd liber, precum și o poziție în matrice, (l, c). Să se spuna cîte elemente 1 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] = 0;
if ( l > 0 && a[l-1][c] == 1 )
fill( l - 1, c );
if ( l < m-1 && a[l+1][c] == 1 )
fill( l + 1, c );
if ( c > 0 && a[l][c-1] == 1 )
fill( l, c - 1 );
if ( c < n-1 && a[l][c+1] == 1 )
fill( l, c + 1 );
}
...
int main() {
...
suma = 0;
if ( a[l][c] == 1 )
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 0. 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] = 0;
if ( a[l-1][c] == 1 )
fill( l - 1, c );
if ( a[l+1][c] == 1 )
fill( l + 1, c );
if ( a[l][c-1] == 1 )
fill( l, c - 1 );
if ( a[l][c+1] == 1 )
fill( l, c + 1 );
}Vectori de directie
In algoritmul de mai sus avem in functia de fill cate un if pentru fiecare vecin al elementului de coordonate (l,c). Putem defini coordonatele vecinilor folosind vectori de directie,, parcurgerea tuturor vecinilor realizandu-se mult mai usor, mai ales in cazul in care pentru un element dat avem mai multi vecini, de pilda cand elementele adiacente pe diagonala sunt considerate si acestea vecini cu un element dat, astfel un element al matricei va avea 8 vecini.
int dl[4] = { -1, 0, 1, 0, -1, 1, 1, -1}; //N, E, S, V, NE, SE, SV, NV
int dc[4] = { 0, 1, 0,-1, 1, 1, -1, -1};
void fill( int l, int c ){
suma++;
a[l][c] = 0; // marcam ca vizitata casuta
for ( int i = 0; i < 4; i++){ // parcurgem toti vecinii si apelam fill pentru vecinii egali cu 1
int x, y;
x = l + dl[i];
y = c + dc[i];
if ( a[x][y] == 1 )
fill ( x, y );
}
}Aplicatie- Problema Fill ( pbinfo ) cu vectori de directie si bordare matrice
Se cere numarul de suprafete pline cu 1
#include <fstream>
using namespace std;
int a[102][102], m,n;
int dl[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0,-1 };
ifstream fin ( "fill.in" );
ofstream fout ( "fill.out" );
void fill( int l, int c ){
a[l][c] = 0; // marcam ca vizitata casuta
for ( int i = 0; i < 4; i++){ // parcurgem toti vecinii si apelam fill pentru vecinii egali cu 1
int x, y;
x = l + dl[i];
y = c + dc[i];
if ( a[x][y] == 1 )
fill ( x, y );
}
}
int main (){
int i, j;
// citire matrice
fin >> m >> n;
for ( i = 1; i <= m; i ++ )
for ( j = 1; j <= n; j ++ )
fin >> a[i][j];
// Bordare matrice : este bordata cu 0, fiind declarata global
// Pentru fiecare element ramas nenul, al matricei, apelez functia de umlmere
int cnt = 0; // numarul de continente
for ( i = 1; i <= m; i ++ )
for ( j = 1; j <= n; j ++ )
if( a[i][j] ){
fill( i, j );
cnt ++;
}
fout << cnt;
}Reducerea memoriei folosite
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 dl[4] = { -1, 0, 1, 0, -1, 1, 1, -1}; //N, E, S, V, NE, SE, SV, NV
int dc[4] = { 0, 1, 0,-1, 1, 1, -1, -1};
int l, c;
int suma;
void fill() {
suma++;
a[l][c] = 0; // marcam ca vizitata casuta
for ( int i = 0; i < 4; i++){ // parcurgem toti vecinii si apelam fill pentru vecinii egali cu 1
l = l + dl[i];
c = c + dc[i];
if ( a[l][c] == 1 )
fill ( l, c );
l = l - dl[i];
c = c - dc[i];
}
}Chiar și în această formă algoritmul va folosi 4 octeți pe apel recursiv imbricat pentru adresa de revenire din funcție.
Aplicatie- Problema Fill ( pbinfo ) cu bordare, vectori de directie si optimizare de memorie
Se cere numarul de suprafete pline cu 1
#include <fstream>
using namespace std;
int a[102][102], m,n;
int dl[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0,-1 };
ifstream fin ( "fill.in" );
ofstream fout ( "fill.out" );
void fill() {
a[l][c] = 0; // marcam ca vizitata casuta
for ( int i = 0; i < 4; i++) // parcurgem toti vecinii si apelam fill pentru vecinii egali cu 1
if ( a[l + dl[i]][c + dc[i]] == 1 ){ // verificam daca vecinul este egal cu 1
l = l + dl[i]; // mutam coordonatele pe coordonatele vecinului
c = c + dc[i];
fill ( ); // reapelam functia de pe coordonatele vecinului
l = l - dl[i]; // readucem coordonatele pe elementul curent
c = c - dc[i];
}
}
int main (){
int i, j;
// citire matrice
fin >> m >> n;
for ( i = 1; i <= m; i ++ )
for ( j = 1; j <= n; j ++ )
fin >> a[i][j];
// Bordare matrice : este bordata cu 0, fiind declarata global
// Pentru fiecare element ramas nenul, al matricei, apelez functia de umlmere
int cnt = 0; // numarul de continente
for ( i = 1; i <= m; i ++ )
for ( j = 1; j <= n; j ++ )
if( a[i][j] ){
fill( i, j );
cnt ++;
}
fout << cnt;
}Aplicații
MosCraciun
Moș Crăciun locuiește la polul nord și pregătește cadouri pentru copii cuminți din clasa a X-a A, ajutat de mai mulți spiriduși. Datorită încălzirii globale, gheața se topește, formându-se mai multe banchize. Spiridușii care se află pe alte banchize decât Moș Crăciun nu-l mai pot ajuta pe acesta, spre disperarea generală.
Scrieți un program care să determine câți spiriduși se află pe aceeași banchiză cu Moș Crăciun și îl pot ajuta în continuare să pregătească cadouri pentru copii cuminți din clasa a X-a A.
#include <fstream>
using namespace std;
int a[102][102], m,n;
int dl[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0,-1 };
int spiridusi, s;
ifstream fin ( "moscraciun.in" );
ofstream fout ( "moscraciun.out" );
void fill( int l, int c ){
int i, x, y;
if ( a[l][c] == 3 )
spiridusi ++;
a[l][c] = 0; // marcam ca vizitata casuta
for ( i = 0; i < 4; i++){ // parcurgem toti vecinii si apelam fill pentru vecinii egali cu 1
x = l + dl[i];
y = c + dc[i];
if ( a[x][y] )
fill ( x, y );
}
}
int main (){
int i, j;
// citire matrice
fin >> m >> n;
for ( i = 1; i <= m; i ++ )
for ( j = 1; j <= n; j ++ )
fin >> a[i][j];
// Bordare matrice : este bordata cu 0, fiind declarata global
// Pentru fiecare element ramas nenul, al matricei, apelez functia de umplmere
for ( i = 1; i <= m; i ++ )
for ( j = 1; j <= n; j ++ )
if( a[i][j] == 2 ){
spiridusi = 0; // numaram spiridusii de pe insula curenta
fill( i, j );
s += spiridusi; // adunam la s nr de spiridusi de pe insula
}
fout << s;
return 0;
}oaste
Pe un continent reprezentat printr-o matrice cu n linii si m coloane se aflá mai multe state, toate aflate in conflict. Astfel, fiecare si-a mobilizat oastea. Elementele matrici memoreazá cäte o cifrá. Doua elemente ínvecinate pe linie sau pe coloaná (nu si pe diagonalá) apartin aceluiasi stat si se numesc regiuni. O pozitie din matrice ce contine cifra 0 este o regiune neutra si nu are soldati, iar pozitia ce contine o cifra c nenula apartine unui stat si are c soldati. Determinati regiunea cu cei mai multi soldati din statul cu cei mai multi soldati.
SAO1
După ce ți-ai dat seama că nu poți învinge nici unul dintre monștrii (din problema SAO), ai decis să te retragi și să devii un fermier. Din banii pentru cumpărarea echipamentului ai cumpărat o parcelă codificată sub forma unei matrice de n linii și m coloane, pentru fiecare zonă cunoscându-se fertilitatea ei. Cum nu ai bani ca să cultivi pământul, dorești să selectezi o parcelă în care toate zonele să aibă aceeași fertilitate, iar fertilitatea totală să fie maximă. Fertilitatea totală a unei parcele este egală cu suma fertilităților zonelor care compun acea parcelă.
Dându-se matricea codificărilor zonelor din teren, să se determine fertilitatea totală maximă a unei parcele în care toate zonele au aceeași fertilitate.
Iesire
Se dă planul unei clădiri pătrate formate din n*n camere, sub forma unei matrice cu n linii și n coloane și elemente 0 sau 1. Camerele marcate cu 0 sunt libere, cel marcate cu 1 sunt inaccesibile și fiecare cameră are o pereche de coordonate, de forma I J, reprezentând linia și coloană pe care este situată camera. Dintr-o cameră liberă se poate trece în altă cameră liberă, cu condiția să se învecineze pe linie sau pe coloană.
Administratorul clădirii primește o listă cu coordonatele a m camere pentru care s-au găsit potențiali chiriași. Nu pot fi închiriate decât camerele libere și accesibile din exteriorul clădirii – adică să existe o succesiune de camere învecinate care începe pe o latură a clădirii și se încheie la camera respectivă.
Pentru fiecare dintre camerele din listă, verificați dacă poate fi închiriată sau nu.
Croco
Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 1 înseamnă uscat, iar 0 înseamnă apă.
Să se plaseze pe fiecare zonă cu uscat un crocodil sau un elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate.
Parcela
Se dau n și m reprezentând dimensiunile unui tablou bidimensional format din elementele 0 si 1. Se definește o parcelă ca fiind o grupare de elemente vecine cu valoarea 1. Să se determine numărul de parcele nr, aria maximă a unei parcele amax și respectiv numărul parcelei cu arie maximă
zona3
Se consideră o matrice cu n linii și m coloane. Spunem că o poziție este liberă dacă elementul de pe linia i și coloana j este egal cu 0 și 1 în caz contrar. Spunem despre mai multe elemente ocupate că formează o zonă, daca elementele se învecinează pe cele patru direcții (sus, jos, dreapta, stânga).
Calculați pentru fiecare zonă numărul de elemente și afișați noua matricea formată prin înlocuirea elementelor egale cu 1 cu numărul de elemente pe care îl are zona din care face parte elementul respectiv.
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ă
Rezolvati problemele ramase nerezolvate din lista de mai sus
Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă.
Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare.
Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel încât numărul de crocodili să fie cât mai mare.
Rezolvări aici [3]
