În mod implicit, elementele unei matrice nu sunt nule atunci când o declarăm, ci sunt aproape aleatorii. Din acest motiv, atunci când lucrăm cu algoritmi precum cel de umplere (Fill) (în curând lecție) sau Algoritmul lui Lee (în curând lecție), trebuie să ne asigurăm că niciodată nu ieșim din matricea noastră (cu liniile de la 1 la n și coloanele de la 1 la m) și că am rămas în spațiul matricei.
Există câteva metode de a face acest lucru, precum crearea unei funcții auxiliare care verifică dacă coordonatele sunt valide (între 1 și n, respectiv între 1 și m), însă acestea pot fi ineficiente atunci când se apelează de multe ori.
De aceea, o metodă simplă de a verifica dacă o poziție se află sau nu într-o matrice este bordarea matricei, lucru ce se poate face în doar câteva linii de cod. Vedem mai jos cum ar trebui să arate o matrice bordată:
Ce înseamnă bordarea unei matrice
De regulă, când lucrăm cu o matrice cu n linii și m coloane, lucrăm cu elementele aflate pe linii de la 1 la n și pe coloane de la 1 la m. Dacă setăm toate elementele de pe linia 0 și n + 1, respectiv coloana 0 și m + 1 cu o anumită valoare, atunci spunem că am bordat matricea și putem să recunoaștem atunci că ne aflăm pe bordura acestei matrice, nu mai putem merge în continuare pe acest drum.
Observație. Elementele aflate pe linia 0 și n + 1, respectiv coloana 0 și m + 1, reprezintă elementele de pe bordura matricei.
Exemplu: algoritmul lui Lee
Un exemplu simplu este algoritmul lui Lee. Dacă în matricea a am notat cu 0 pozițiile în care se poate trece și cu 1 pozițiile blocate (de un perete, de exemplu), atunci putem să bordăm matricea cu elemente de 1, astfel plasând pereți în jurul matricei.
Bordarea se poate face cu orice valoare, însă se recomandă folosirea unei valori sugestive (cum mai devreme am folosit valoarea 1, aceeași pentru a marca obstacolele).
Bordarea unei matrice în C++ (secvență de cod)
Folosind două structuri repetitive de tip for, putem să setăm elementele de pe bordura matricei cu ușurință:
for(int i = 1; i <= n; i++) {
a[i][0] = 1;
a[i][m + 1] = 1;
}
for(int j = 1; j <= m; j++) {
a[0][j] = 1;
a[n + 1][j] = 1;
}
Exemplu vizual
Iată un exemplu de matrice, cu n = m = 7 linii și coloane. Inițial, matricea nu este bordată deloc:
Mai apoi, setăm elementele de pe liniile și coloanele 0 și 8 cu 1, astfel bordând matricea. Bordura matricei are culoarea mai deschisă.