Dan: /* BFS Continuare */

2015-10-22T13:22:31Z

BFS Continuare

New page

= Recapitulare materie =

== Secvență bitonă prin rotație ==
Verificare secvență bitonă prin rotație. O secvență este bitonă dacă mai întîi crește și apoi, eventual, descrește. O secvență bitonă prin rotație este o secvență care fie este bitonă, fie poate fi făcută bitonă prin rotații succesive. Problema trebuie rezolvată fără a folosi vectori, similar cu problema secvenței crescătoare prin rotație. Soluție liniară. Dacă ați înțeles algoritmul încercați-vă forțele rezolvînd problema [http://varena.ro/problema/bitona secvență bitonă].

== Problema selecției ==
Dat un șir de <tt>n</tt> numere și o poziție <tt>k</tt> în acel șir să se spună ce element s-ar afla pe acea poziție dacă șirul ar fi sortat. Aplicăm repetat pivotarea quicksort. Calcul aproximativ al complexității pe cazul mediu: este O(n), în loc de O(n log n) dacă am fi făcut sortare. Dacă ați înțeles algoritmul încercați-vă forțele rezolvînd problema [http://varena.ro/problema/selectie selecție].

== Elementul majoritar ==
Dat un vector cu <tt>n</tt> elemente să se spună dacă conține un element majoritar. Un element majoritar este un element care apare de cel puțin <tt>n/2 + 1</tt> ori. Încercați să dați o soluție mai bună decît sortarea. Am discutat variante de algoritmi:
* Forță brută: luăm fiecare element din vector și vedem de cîte ori apare. Complexitate O(n2).
* Prin sortare: sortăm vectorul și căutăm subsecvența de elemente egale de lungime maximă. Complexitate: O(n2) cu sortare prin selecție, O(n log n) cu quicksort.
* Algoritmul optim: considerăm primul element drept candidat, iar apoi parcurgem vectorul, numărînd de cîte ori apare candidatul. De fiecare dată cînd apare un element diferit de candidat decrementăm contorul. Dacă contorul ajunge negativ repornim procedura cu elementul curent drept nou candidat. În final dacă candidatul are măcar o apariție îl verificăm de cîte ori apare în vector. Complexitate O(n).

Dacă ați înțeles algoritmul încercați-vă forțele rezolvînd problema [http://varena.ro/problema/majoritar elementul majoritar].

== Paranteze ==
Verificare expresie cu paranteze. Se dă o expresie cu paranteze rotunde, pătrate și acolade: <nowiki>(), [] și {}</nowiki>. Ele pot să apară în orice ordine, adică și <nowiki>)</nowiki> după <nowiki>]</nowiki>. Să se spună dacă o expresie este corectă. Exemple: <tt><nowiki>([()[]()]())[]</nowiki></tt> este corectă, <tt><nowiki>([)], )(, ([()]</nowiki></tt> nu sînt corecte. Am discutat despre cazul mai simplu, în care avem doar paranteze rotunde, apoi am generalizat la cazul cu mai multe tipuri de paranteze, folosind o stivă.

== Baze de numerație ==
Un ''sistem de numerație'' este un mod de a exprima numerele. Cu alte cuvinte o notație matematică pentru a reprezenta numerele folosind cifre sau alte simboluri într-o manieră consecventă. Sistemul de numerație este cel care face ca simbolurile "11" să fie interpretate ca simbolul binar al lui trei, simbolul zecimal al lui unsprezece, sau simbolul altor numere în diferite baze.

Un sistem de numerație:

* Reprezintă o mulțime utilă de numere (de ex. toți întregii, sau numerele raționale)
* Reprezintă unic fiecare număr
* Ideal, ar trebui să reflecte structura algebrică și aritmetică a numerelor

=== Conversia de la baza 10 la baza 2 ===
Pentru a converti un număr ''n'' din baza 10 în baza 2 îl vom împărți la 2 în mod repetat, pîna ce obținem cîtul zero. Apoi vom colecta resturile obținute de la ultimul către primul. Aceste resturi sînt cifrele numărului în baza doi, de la stînga la dreapta.

==== Exemplul 1 ====
Să convertim numărul ''26'' la baza 2:

''26 = 2×13 + 0'' 
''13 = 2×6 + 1'' 
''6 = 2×3 + 0'' 
''3 = 2×1 + 1'' 
''1 = 2×0 + 1'' 
 
''26(10) = 11010(2)''

==== Exemplul 2 ====
Să convertim numărul ''37'' la baza 2:

''37 = 2×18 + 1'' 
''18 = 2×9 + 0'' 
''9 = 2×4 + 1'' 
''4 = 2×2 + 0'' 
''2 = 2×1 + 0'' 
''1 = 2×0 + 1'' 
 
''37(10) = 100101(2)''

=== Conversia de la baza 2 la baza 10 ===
Această conversie se poate face direct, scriind fiecare cifră binară explicit înmulțită cu puterea corespunzătoare a lui 2.

==== Exemplul 3 ====
Să convertim numărul ''100101'' din baza 2 în baza 10:

''100101(2) = 1×25 + 0×24 + 0×23 + 1×22 + 0×21 + 1×20'' 
''100101(2) = 1×32 + 0×16 + 0×8 + 1×4 + 0×2 + 1×1'' 
''100101(2) = 32 + 4 + 1'' 
''100101(2) = 37(10)'' 

Deși această metodă a evaluării directe prin dezvoltarea numărului cu puterile lui doi este mai simplu de înțeles, există un algoritm ceva mai rapid. Începînd cu rezultatul ''0'', parcurgem cifrele binare de la stînga la dreapta. Pentru fiecare cifră a numărului de la intrare vom înmulți rezultatul cu doi și vom aduna cifra la rezultat.

==== Exemplul 4 ====
Să convertim numărul ''11010'' din baza 2 în baza 10 folosind acest algoritm:

''0×2 + 1 = 1'' 
''1×2 + 1 = 3'' 
''3×2 + 0 = 6'' 
''6×2 + 1 = 13'' 
''13×2 + 0 = 26'' 
 
''11010(2) = 26(10)'' 

Acesta este algoritmul pe care îl vom prefera pentru conversia numerelor din baza 2 în baza 10.

=== Conversie de la baza 10 la baza 2 ===
Se citește <tt>n</tt> de maxim 18 cifre. Să se afișeze reprezentarea lui în baza 2.

Varianta clasică, despre care am vorbit mai sus, este cea în care reținem resturile împărțirii repetate la doi și apoi le afișăm în ordine inversă:

<syntaxhighlight>#include <stdio.h>

int cifre[60]; // 60 de cifre binare = 18 cifre zecimale

int main() {
FILE *fin, *fout;
int m, i;
long long n; // 18 cifre inseamna long long

fin = fopen( "b10b2.in", "r" );
fscanf( fin , "%lld", &n );
fclose( fin );

m = 0;
while ( n > 0 ) {
cifre[m] = n % 2; // extragem pe rind resturile impartirii la 2
m++;
n /= 2;
}

fout = fopen( "b10b2.out", "w" );
for ( i = m - 1; i >= 0; i-- ) // afisam resturile in ordine inversa
fprintf( fout, "%d", cifre[i] );
fprintf( fout, "\n" );
fclose( fout );

return 0;
}</syntaxhighlight>

=== Conversie de la baza 2 la baza 10 ===
La intrare avem o înșiruire de caractere 0 și 1, neseparate de spații și terminate cu final de linie. Ele reprezintă un număr în baza 2 de cel mult 60 de cifre binare. Să se convertească acest număr la baza 10 și să se afișeze.

Vom proceda precum am discutat mai sus. Vom citi cifrele binare una cîte una și le vom adăuga la coada lui <tt>n</tt>, înmulțindu-l pe acesta cu doi și apoi adunînd cifra. Iată programul:

<syntaxhighlight>#include <stdio.h>

int main() {
FILE *fin, *fout;
long long n; // 18 cifre inseamna long long
char ch;

fin = fopen( "b2b10.in", "r" );
n = 0;
ch = fgetc( fin );
while( ch != '\n' ) {
n = n * 2 + ch - '0';
ch = fgetc( fin );
}
fclose( fin );

fout = fopen( "b2b10.out", "w" );
fprintf( fout, "%lld\n", n );
fclose( fout );

return 0;
}</syntaxhighlight>

=== Aplicație: submulțimile unei mulțimi ===
''Aceasta este o problemă clasică în matematică și informatică.''

Rezolvați în clasă următorul exercițiu: să se afișeze toate submulțimile nevide ale mulțimii <nowiki>{ 1, 2, 3, ..., n }</nowiki>.

Cum abordăm această problemă? La prima vedere pare foarte grea. Va trebui, probabil, să afișăm toate submulțimile de un element. Aceasta e simplu. Apoi cele de două elemente. Tot simplu, vom selecta perechile cu două bucle <tt>for</tt>. Apoi cele cu trei elemente. Hmmm, de data asta avem nevoie de trei bucle <tt>for</tt>. Apoi de patru. Apoi de cinci. Cînd se oprește? Răspunsul depinde de <tt>n</tt>. Dar stai! Nu putem scrie un număr variabil de bucle <tt>for</tt> una într-alta!

Ne trebuie o altă abordare. Vom codifica mulțimile. Cum? Foarte simplu: folosind vectorul lor caracteristic. Pentru fiecare element al mulțimii, de la 1 la <tt>n</tt>, vom avea un element în vectorul <tt>v</tt>. Pentru o submulțime dată <tt>v[i]</tt> este 1 dacă elementul <tt>i</tt> apare în submulțime.

Acest mod de codificare demonstrează un lucru interesant: numărul de submulțimi al unei mulțimi, incluzînd mulțimea vidă, este 2n. Interesant!

Cum vom folosi acest vector? Destul de neclar. Ne-ar trebui un mod în care să variem toate elementele sale de la zero la unu. Și iar ne întoarcem la buclele <tt>for</tt> una într-alta. Dar există un mod natural în care elementele pot trece prin toate combinațiile posibile de 0 și 1: dacă în loc să folosim un vector cu <tt>n</tt> elemente folosim un număr binar cu <tt>n</tt> cifre. Dacă pornim cu numărul binar de la zero și îl incrementăm pînă ce ajungem la 2n cele <tt>n</tt> cifre ale sale vor trece prin toate configurațiile posibile. Exact ce ne dorim!

În concluzie, care este algoritmul? Iată-l descris mai jos:

<pre>1. Pentru i de la 1 la 2^n - 1
1.1 Descompune i în baza 2
1.2 Pentru fiecare cifră binară 1 care se află pe poziția j
1.2.1 Afișează j
1.3 Sfîrșit de submulțime, treci la linia următoare</pre>

Remarcați că algoritmul nu folosește vectori! Vă invit să rezolvați problema [http://varena.ro/problema/submultimi1 submulțimi1] la vianuarena, folosind acest algoritm. După ce o rezolvați, pentru verificare, iată codul complet mai jos:

<syntaxhighlight lang="C" style="border: dashed">#include <stdio.h>

int main() {
FILE *fin, *fout;
int n, m, i, p2max, p;

fin = fopen( "submultimi1.in", "r" );
fscanf( fin, "%d", &n );
fclose( fin );

p2max = 1; // calculam 2^n, numarul pina unde trebuie sa numaram
for ( i = 0; i < n; i++ )
p2max *= 2;

fout = fopen( "submultimi1.out", "w" );
for ( i = 1; i < p2max; i++ ) { // numaram de la 1 la 2^n exclusiv
m = i; // copiem contorul, sa nu il pierdem
for ( p = 1; p <= n; p++ ) { // obtinem pe rind cifrele binare
if ( m % 2 == 1 ) // 1 inseamna ca pozitia apartine multimii
fprintf( fout, "%d ", p ); // afisam pozitia cifrei 1, p
m /= 2;
}
fprintf( fout, "\n" ); // am afisat o submultime, linie noua
}
fclose( fout );

return 0;
}</syntaxhighlight>

== Calculul multiplicității unui număr în ''n''<nowiki>!</nowiki> ==

=== Calculul multiplicității unui număr prim în ''n''<nowiki>!</nowiki> ===
Matematicianul [http://en.wikipedia.org/wiki/Adrien-Marie_Legendre Adrien-Marie_Legendre] a descoperit că multiplicitatea (exponentul) unui număr prim ''p'' care apare în descompunerea în factori primi a lui ''n''<nowiki>!</nowiki> poate fi exprimată exact ca:

:<math>Exp(p,n!) = \left \lfloor \frac{n}{p} \right \rfloor + \left \lfloor \frac{n}{p^2} \right \rfloor + \left \lfloor \frac{n}{p^3} \right \rfloor + \cdots = \sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor .</math>

Acest fapt se bazează pe numărarea factorilor ''p'' ai întregilor de la 1 la ''n''. Numărul multiplilor lui ''p'' în numerele de la 1 la ''n'' este <math>\textstyle \left \lfloor \frac{n}{p} \right \rfloor</math>; dar această formulă numără numerele cu doi factori ''p'' o singură dată. De aceea trebuie să mai numărăm încă <math>\textstyle \left \lfloor \frac{n}{p^2} \right \rfloor</math> factori ai lui ''p''. În mod similar pentru trei, patru, cinci factori, pînă la infinit. Însă suma este finită deoarece ''p'' ''i'' este mai mic sau egal cu ''n'' într-un număr finit de valori ale lui ''i'', drept care funcția parte întreagă va fi zero pentru toate celelalte valori.

Cînd scriem programul pentru calculul exponentului ne vom opri la acel ''i'' pentru care ''pi > n''.

=== Calculul multiplicității unui număr prim la o putere în ''n''<nowiki>!</nowiki> ===
Este simplu de demonstrat că dacă avem un număr prim ''p'' la o putere ''k'' atunci multiplicitatea lui ''pk'' în ''n''<nowiki>!</nowiki> este

:<math>Exp(p^k,n!) = \frac{Exp(p,n!)}{k}</math>

=== Calculul multiplicității unui număr oarecare în ''n''<nowiki>!</nowiki> ===
Este simplu să arătăm că dacă avem un număr ''a'' a cărui descompunere în factori primi este

:''a = p1k1 • p2k2 • … • pmkm''

atunci multiplicitatea (exponentul) lui ''a'' în ''n''<nowiki>!</nowiki> este

:<math>Exp(a,n!) = min(Exp(p_1^{k_1},n!),Exp(p_2^{k_2},n!),\ldots,Exp(p_m^{k_m},n!))</math>

sau

:<math>Exp(a,n!) = min(\frac{Exp(p_1,n!)}{k_1},\frac{Exp(p_2,n!)}{k_2},\ldots,\frac{Exp(p_m,n!)}{k_m})</math>

== Memoizare ==
''Memoizarea'' este o metodă de a face un program mai rapid fără a-i schimba modul în care el funcționează. Ideea ei este ca atunci cînd efectuăm un calcul scump să păstrăm valoarea calculată într-un tablou pentru a economisi timp în cazul cînd în viitor vom avea din nou nevoie de acea valoare. Să o învățăm prin exemple.
=== Exemplu ===
Să presupunem că ni se dau ''n'' numere ''a0, a1, ..., an-1'' și ni se cere să afișăm factorialele acelor numere modulo ''k''. O soluție naivă ar putea fi următoarea:

<syntaxhighlight>for ( i = 0; i < n; i++ ) {
p = 1;
for ( j = 2; j < a[i]; j++ )
p = (p * j) % k;
printf( "%d ", p );
}</syntaxhighlight>

Să calculăm complexitatea tipului de execuție: pentru fiecare număr ''ai'' vom face ''O(ai)'' înmulțiri, drept pentru care complexitatea soluției este ''O(suma(ai))''. Desigur că putem face un program mai eficient care calculează un vector <tt>fact[i]</tt> unde <tt>fact[i]</tt> este ''i''! (''i'' factorial). Acest vector se poate calcula în ''O(max(ai))'', după care printr-o parcurgere a numerelor ''ai'' vom putea calcula rezultatul ceea ce duce la o complexitate optimă de ''O(n + max(ai))''.

Însă în unele cazuri nu este ușor să schimbăm radical programul pentru a scrie o soluție mai eficientă decît soluția naivă. Cum putem folosi tehnica ''memoizării'' pentru a modifica foarte puțin soluția brută și a o aduce la complexitate optimă? Am putea ca de fiecare dată cînd calculăm ''ai''! să păstrăm rezultatul într-un vector la poziția ''ai''. Vom păstra, de asemenea și toate factorialele intermediare calculate pe parcurs. Atunci cînd vom avea nevoie de calculul unui factorial vom merge în jos pînă la primul factorial calculat. Iată implementarea:

<syntaxhighlight>fact[1] = 1; // pentru a ne opri la final
for ( i = 0; i < n; i++ ) {
j = a[i];
while ( fact[j] == 0 ) // cautam in jos primul factorial calculat
j--;
p = fact[j];
for ( j++; j <= a[i]; j++ ) // calculam toate valorile pina la a[i]
fact[j] = (fact[j-1] * j) % k;
printf( "%d ", fact[j] );
}</syntaxhighlight>

Ce complexitate în timp are această soluție? Deoarece ea nu repetă calcule în vectorul <tt>fact</tt> rezultă că fiecare element al vectorului va fi calculat cel mult odată, în timp ''O(1)'', deci soluția va fi optimă, ''O(n+max(ai))''. Observați că am obținut aceeași complexitate optimă dar fără a schimba structura algoritmului nostru naiv, ci doar memorînd rezultate parțiale într-un vector. Aceasta este exact ideea memoizării.

== Funcții în limbajul C ==
Funcțiile permit programelor complicate să fie parcelate în blocuri mici, fiecare din ele fiind mai ușor de scris, citit și modificat (întreținut). Am întîlnit deja funcția <tt>main()</tt> și am folosit funcții de intrare ieșire, precum și funcții matematice din bibliotecile standard. Vom vedea în continuare cum putem să scriem propriile noastre funcții.

=== De ce funcții ===
* Pentru a nu repeta cod.
* Pentru organizare, citibilitate, ușurinta înțelegerii codului și întreținerea codului.
* Recursivitate, precum vom vedea anul următor.

=== Sintaxa: cum scriem o funcție ===
==== Sintaxa (simplificare) ====
<pre><tip returnat> <nume funcție>(<tip1> <var1>, <tip2> <var2>, ..., <tipn> <varn>) {
... declarații variabile ...
... cod funcție ...
return <valoare return>; // dacă tipul returnat nu este 'void'
}
</pre>
==== Parametri și valoarea returnată ====
* Parametri, valoare returnată
* Transmisia parametrilor se face numai prin copiere, pe stiva sistem
** Ce afișează următorul program:
<syntaxhighlight>void inc( int a ) {
a++;
}

int main() {
int x = 0;
inc( x );
printf( "%d", x );
return 0;
}</syntaxhighlight>
* Valoarea returnată, prin copiere pe stiva sistem
* Cum modificam parametrii, operatorii <tt>&</tt> si <tt>&</tt>; ar fi bine să evitați, deocamdată. Exemplu: functia swap.
* Transmisie vectori ca parametri; vom transmite și lungimea; vectorul și lungimea lui sînt componente inseparabile ale tipului de date abstract.
** Ce se întîmplă dacă modificăm elementele vectorului în funcție?
** Ce se întîmplă dacă modificăm lungimea vectorului în funcție?
* Declarații de variabile și vizibilitatea acestora. Așezarea lor pe stivă.
* Conversia de tip cînd chemăm funcția cu alte tipuri decît cele declarate.

==== Apelul ====
O funcție este apelată astfel: <tt>numeFunctie( valoare1, valoare2, ..., valoaren );</tt>

= Tema =
* Implementați algoritmii din clasă la vianuarena: [http://varena.ro/problema/bitona bitonă], [http://varena.ro/problema/majoritar majoritar], [http://varena.ro/problema/selectie selecție]
* [http://varena.ro/runda/2014-09-30-clasa-7-tema-2 Tema 2 clasa a 7a]
* '''Opţional:''' Tema de la clasa a 8a
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_2_-_30_sep_2014]

= Lecția 3 - Recursivitate (extensie) =

== Interclasarea a doi vectori prin recursivitate ==

Dându-se 3 vectori:
* vectorul 1 prin pointeri către începutul și după sfârșitul lui;
* vectorul 2 prin pointeri către începutul și după sfârșitul lui;
* vectorul 3 printr-un pointer către începutul lui
și garantându-se că:
* elementele vectorilor 1 și 2 sunt în ordine crescătoare;
* vectorul 3 are rezervat un spațiu cel puțin egal cu suma lungimilor vectorilor 1 și 2,
să se scrie o funcție recursivă care primește ca parametri cei 3 vectori și îi interclasează pe primii 2 în al treilea.

<syntaxhighlight>
void interclaseaza(
int* v1Inc, int* v1Sf,
int* v2Inc, int* v2Sf,
int* v3Inc) {
if (v1Inc != v1Sf && v2Inc != v2Sf) {
if (*v1Inc < *v2Inc) {
*v3Inc = *v1Inc;
interclaseaza(v1Inc + 1, v1Sf, v2Inc, v2Sf, v3Inc + 1);
} else {
*v3Inc = *v2Inc;
interclaseaza(v1Inc, v1Sf, v2Inc + 1, v2Sf, v3Inc + 1);
}
} else if (v1Inc != v1Sf) {
*v3Inc = *v1Inc;
interclaseaza(v1Inc + 1, v1Sf, v2Inc, v2Sf, v3Inc + 1);
} else if (v2Inc != v2Sf) {
*v3Inc = *v2Inc;
interclaseaza(v1Inc, v1Sf, v2Inc + 1, v2Sf, v3Inc + 1);
}
}
</syntaxhighlight>

= Temă =

Opțional: Să se rezolve cerința 2 din problema [http://varena.ro/problema/portofel Portofel] prin recursivitate.

= BFS Continuare =

== Problema Alee ==

=== Cu reconstituirea drumului ===
<syntaxhighlight>
#include <stdio.h>
#include <assert.h>

#define MAX_N 175

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

// doar primele 4 directii sunt folosite
int dirLin[] = { 1, -1, 0, 0, 1, 1, -1, -1};
int dirCol[] = { 0, 0, 1, -1, 1, -1, 1, -1};

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

int main(void) {
FILE* in = fopen("alee.in", "r");
FILE* out = fopen("alee.out", "w");
int N, M;
int i, j;
int l, c;

// citirea datelor
fscanf(in, "%d %d", &N, &M);
for (i = 0; i < M; ++i) {
fscanf(in, "%d %d", &l, &c);
mat[l][c] = 1; // obstacol
}
int L1, C1, L2, C2;
fscanf(in, "%d %d", &L1, &C1);
fscanf(in, "%d %d", &L2, &C2);
// bordarea matricei
for (c = 0; c <= N + 1; c++) {
mat[0][c] = 1;
mat[N + 1][c] = 1;
}
for (l = 1; l <= N; l++) {
mat[l][0] = 1;
mat[l][N + 1] = 1;
}

// calcularea solutiei
for (i = 0; i <= N + 1; ++i) {
for (j = 0; j <= N + 1; ++j) {
dist[i][j] = 0;
}
}
dist[L1][C1] = 1;
int vechi = 0;
inceput = sfarsit = 0;
linie[sfarsit] = L1;
coloana[sfarsit] = C1;
sfarsit++;
while (inceput < sfarsit && dist[L2][C2] == 0) {
l = linie[inceput];
c = coloana[inceput];
inceput++;
for (i = 0; i < 4; ++i) {
if (mat[l + dirLin[i]][c + dirCol[i]] == 0 && dist[l + dirLin[i]][c + dirCol[i]] == 0) {
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
fprintf(out, "%d\n", dist[L2][C2]);

// reconstituirea drumului
l = L2;
c = C2;
fprintf(out, "%d %d\n", l, c);
for (j = dist[l][c]; j > 1; j--) {
assert(dist[l][c] == j);
i = 0;
while (dist[l + dirLin[i]][c + dirCol[i]] != dist[l][c] - 1) {
// Conditia i < 4 nu este necesara deoarece tot timpul
// va exista cel putin un vecin.
i++;
}
l = l + dirLin[i];
c = c + dirCol[i];
fprintf(out, "%d %d\n", l, c);
}
fclose(in);
fclose(out);
return 0;
}
</syntaxhighlight>

=== Cu operații specifice structurii coadă ===
<syntaxhighlight>
#include <assert.h>

#define MAX_N 175

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

// doar primele 4 directii sunt folosite
int dirLin[] = { 1, -1, 0, 0, 1, 1, -1, -1};
int dirCol[] = { 0, 0, 1, -1, 1, -1, 1, -1};

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

void push(int l, int c) {
linie[sfarsit] = l;
coloana[sfarsit] = c;
sfarsit++;
}

int topL() {
return linie[inceput % SIZE];
}

int topC() {
return coloana[inceput % SIZE];
}

void pop() {
inceput++;
}

int isEmpty() {
return inceput == sfarsit;
}

int size() {
return sfarsit - inceput;
}

int main(void) {
FILE* in = fopen("alee.in", "r");
FILE* out = fopen("alee.out", "w");
int N, M;
int i, j;
int l, c;

// citirea datelor
fscanf(in, "%d %d", &N, &M);
for (i = 0; i < M; ++i) {
fscanf(in, "%d %d", &l, &c);
mat[l][c] = 1; // obstacol
}
int L1, C1, L2, C2;
fscanf(in, "%d %d", &L1, &C1);
fscanf(in, "%d %d", &L2, &C2);
for (c = 0; c <= N + 1; c++) {
mat[0][c] = 1;
mat[N + 1][c] = 1;
}
for (l = 1; l <= N; l++) {
mat[l][0] = 1;
mat[l][N + 1] = 1;
}

// calcularea solutiei
for (i = 0; i <= N + 1; ++i) {
for (j = 0; j <= N + 1; ++j) {
dist[i][j] = 0;
}
}
dist[L1][C1] = 1;
int vechi = 0;
inceput = sfarsit = 0;
linie[sfarsit] = L1;
coloana[sfarsit] = C1;
sfarsit++;
while (!isEmpty() && dist[L2][C2] == 0) {
l = topL();
c = topC();
pop();
for (i = 0; i < 4; ++i) {
if (mat[l + dirLin[i]][c + dirCol[i]] == 0 && dist[l + dirLin[i]][c + dirCol[i]] == 0) {
dist[l + dirLin[i]][c + dirCol[i]] = dist[l][c] + 1;
push(l + dirLin[i], c + dirCol[i]);
}
}
++vechi;
}

// afisarea solutiei
fprintf(out, "%d\n", dist[L2][C2]);

// reconstituirea drumului
l = L2;
c = C2;
fprintf(out, "%d %d\n", l, c);
for (j = dist[l][c]; j > 1; j--) {
assert(dist[l][c] == j);
i = 0;
while (dist[l + dirLin[i]][c + dirCol[i]] != dist[l][c] - 1) {
// Conditia i < 4 nu este necesara deoarece tot timpul
// va exista cel putin un vecin.
i++;
}
l = l + dirLin[i];
c = c + dirCol[i];
fprintf(out, "%d %d\n", l, c);
}
fclose(in);
fclose(out);
return 0;
}
</syntaxhighlight>

=== Cu coadă implementată circular ===
<syntaxhighlight>
...

#define SIZE (2 * (MAX_N + MAX_N))

int linie[SIZE];
int coloana[SIZE];
int inceput, sfarsit;

void push(int l, int c) {
linie[sfarsit % SIZE] = l;
coloana[sfarsit % SIZE] = c;
sfarsit++;
}

int topL() {
return linie[inceput % SIZE];
}

int topC() {
return coloana[inceput % SIZE];
}

void pop() {
inceput++;
}

int isEmpty() {
return inceput == sfarsit;
}

int size() {
return sfarsit - inceput;
}

...
</syntaxhighlight>

Clasa7 - Revision history

Dan: /* BFS Continuare */