Algoritm de fill sau “de umplere”
- Ce este si ce face acest algoritm?
Acest algoritm este un algoritm ce se foloseste de obicei atunci cand avem de lucru cu o matrice. Ce facest acest algoritm? Are multe aplicatii, dar una din cele mai practice este atunci cand determinam numarul elementelor dintr-o matrice care respecta o anumita conditie. Haideti sa ne uitam peste un exemplu si sigur veti intelege
Problema ferma – Olimpiada Judeteana de Informatica 2014 – clasa a 10-a
Avand o matrice cu mai multe elemente, cum este cea de mai sus. Noi trebuie sa determinam care este suprafata cea mai mare ocupata de aceste litere. In acest gaz algoritmul de fill se potriveste perfect! Cea mai mare suprafata ocupata este de 11 unitati (litera v). Cum functioneaza acest algoritm? Se duce la un element, dupa care “se extinde” la toti vecinii lui pana cand toti vecinii nu mai indeplinesc conditia esentiala (sa aiba aceeasi litera ca si elementul de la care s-a pornit).
-
Prezentarea generala
Algoritmul de fill este un algoritm special prin care pargcurgem matricea si determinam cate parti distincte avem intr-o problema. De exemplu, acum avem 11 “parti” diferite. In general acest algoritm se aplica doar pe probleme specifice. Una dintre aceste probleme specifice a fost problema “ferma”, data in 2014 in cadrul Olimpiadei Judetene de Informatica. A fost problema care m-a calificat la nationala, am invatat algoritmul de fill cu cateva seri inainte, sper sa va prinda si voua bine acest articol!
-
Problema ferma3
Un fermier deţine o fermă de formă dreptunghiulară cu lungimea m metri şi lăţimea n metri. Respectând principiul rotaţiei culturilor, fermierul şi‑a realizat un plan pentru semănarea culturilor în noul an. Astfel ,el a desenat un dreptunghi pe care l-a împărţit în m * n celule, fiecare corespunzând unui metru pătrat, şi a colorat în culori diferite zonele care corespund unor culturi diferite. O cultură poate fi semănată pe mai multe parcele. Două celule care au o latură comună aparţin aceleiaşi parcele dacă au aceeaşi culoare (sunt însămânţate cu aceeaşi cultură). Fermierul are posibilitatea să irige o sigură parcelă şi doreşte să aleagă parcela cu cea mai mare suprafaţă.
-
Vectorii de deplasare
Dupa cum am discutat si in Algoritmul lui Lee in C++ , se aplica “vectorii de deplasare”. Trebuie mai intai sa depistam daca este vorba despre o problema in care luam 4 vecini in considerare, sau 8 vecini. Luam 4 vecini atunci cand se mentioneaza doar directiile “Nord, Sud, Est, Vest”. Astfel, dupa cum urmeaza, avem nordul (0,1), sudul (0,-1), vestul (1,0) si estul (-1,0). Cei doi vectori sunt:
int di[4] = {1,0,-1,0};
int dj[4] = {0,1,0,-1};
-
Citirea valorilor din problema
In datele de intrare avem 3 numere: V, M si N. V reprezinta prima sau a doua cerinta din problema, iar M si N reprezinta dimensiunea matricei. Mai departe vom rezolva doar cerinta 1 deoarece scoate in evidenta mai bine Algoritmul de fill (sau de umplere).
-
Functia OK
Un detaliu foarte important este faptul ca vom construii doua matrici. O matrice in care stocam numerele citite la intrare, si o matrice in care vom memora numarul zonei in care am fost. Astfel incat functia OK permite doar elemente ce sunt in interiorul matricei si elemente ce nu au fost deja atribuite unei “insule”.
bool OK(int i, int j)
{
if(i < 1 || j < 1 || i > N || j > M)
return false;
if(matriceFill[i][j] != 0)
return false;
return true;
}
-
Algoritmul de fill
void algFill(int x, int y)
{
matriceFill[x][y] = numarul_zonei; //Memoram in matricea Fill, numarul zonei in care suntem acum
d[numarul_zonei]++; //Incrementam cate elemente fac parte in acest moment din insula curenta
for(int i = 0; i < 4; i++)
{
int noul_i = x + di[i]; //Formam noul i pe care il vom accesa
int noul_j = y + dj[i]; //Formam noul j pe care il vom accesa
if(OK(noul_i, noul_j) && matrice[x][y] == matrice[noul_i][noul_j]) // Daca elementul curent este corespunzator, executam algoritmul
algFill(noul_i, noul_j); // Apelam recursiv algoritmul de Fill
}
}
In momentul in care algoritmul de Fill primeste un element, salvam numarul zonei in care se afla in matriceFill. Urmatorul pas este sa incrementam numarul elementelor ce se afla in acea zona. In d[4] – retinem toate elementele ce fac parte din insula 4.
Mai departe parcurgem vecinii, si formam noile coordonate. Daca elementul corespunde cerintelor algoritmului (vecinii si elementul curent sunt egali), executam algoritmul recursiv.
-
Algoritmul problemei ferma3 (infoarena.ro)
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("ferma3.in");
ofstream fout("ferma3.out");
const int NMAX = 405;
int N, M, V, numarul_zonei;
int matrice[NMAX][NMAX];
int matriceFill[NMAX][NMAX];
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};
int d[NMAX*NMAX];
bool OK(int i, int j)
{
if(i < 1 || j < 1 || i > N || j > M)
return false;
if(matriceFill[i][j] != 0)
return false;
return true;
}
void algFill(int x, int y)
{
matriceFill[x][y] = numarul_zonei; //Memoram in matricea Fill, numarul zonei in care suntem acum
d[numarul_zonei]++; //Incrementam cate elemente fac parte in acest moment din insula curenta
for(int i = 0; i < 4; i++)
{
int noul_i = x + di[i]; //Formam noul i pe care il vom accesa
int noul_j = y + dj[i]; //Formam noul j pe care il vom accesa
if(OK(noul_i, noul_j) && matrice[x][y] == matrice[noul_i][noul_j]) // Daca elementul curent este corespunzator, executam algoritmul
algFill(noul_i, noul_j); // Apelam recursiv algoritmul de Fill
}
}
int main()
{
int maxim = 0;
fin >> V >> N >> M;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
char c;
fin >> c;
matrice[i][j] = (int) c;
}
}
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
if(!matriceFill[i][j])
{
numarul_zonei++;
algFill(i, j);
if(maxim < d[numarul_zonei])
maxim = d[numarul_zonei];
}
}
}
if(V == 1)
fout << maxim << "\n";
}
