Bella: /* Tema */

2019-03-06T12:36:21Z

Tema

New page

=BFS ( Algoritmul lui Lee )=
<syntaxhighlight>
/*
Fie o harta reprezentata de catre o matrice de dimensiuni n * m. Elementele matricei vor fi: 0 pentru celule cu obstacole,
1 pentru celule goale.
Sa se determine punctul cel mai indepartat de pe harta fata de un punct dat P (x1,y1).
Lungimea drumului va fi determinata de catre numarul de casute pe care trebuie sa le traversez, plecând din P, pana la acel punct,
fara a trece prin casute in care avem obstacole.
*/
#include <stdio.h>
#define MAX_N 100
#define MAX_M 100

int a[MAX_N + 2][MAX_M + 2]; //adaugam 2 linii, doua coloane pentru bordare
int dist[MAX_N + 2][MAX_M + 2]; //matricea in care calculam distantele de la
// 812 //Ordinea in care am definit vecinii
// 7x3
// 654
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = { 0, 1, 1, 1, 0,-1,-1, -1};

int lin[MAX_N * MAX_M];
int col[MAX_N * MAX_M];
int vf, sf;
int main(void) {
int n, m, i, j, l, c ;
FILE *fin = fopen( "mat.in", "r");
// citirea datelor; construim harta in matricea a; matricea este initializata cu 0 deci este deja bordata.
fscanf(fin, "%d %d", &n, &m);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
fscanf(fin, "%d", &a[i][j]);

int L, C;
fscanf(fin,"%d %d", &L, &C); //punctul de la care doresc calculul distantelor

// calcularea solutiei;
for (i = 0; i <= n + 1; ++i)
for (j = 0; j <= m + 1; ++j)
dist[i][j] = -1; //initial toate distantele sunt necalculate
dist[L][C] = 0; //distanta de la punctul initial la el insusi este 0

vf = sf = 0; //initial coada e vida; varful cozii coincide cu sfarsitul ei; sf tine minte cate elem am in coada
lin[sf] = L; //introducem coordonatele punctului de plecare in coada
col[sf] = C;
sf++; //coada contine 1 element acum
while (vf < sf) { //cata vreme mai am elemente in coada de analizat
for (i = 0; i < 8; ++i){ //vizitam toate elementele vecine elementului curent ( cel de la coord stocate in varful cozii)
l=lin[vf]+dx[i]; //coordonatele vecinului i
c=col[vf]+dy[i];
if (a[l][c] == 1 && dist[l][c] == -1) { //daca elementul vecin nu are obstacol si distata pana la el nu este calculata
dist[l][c] = dist[lin[vf]][col[vf]] + 1; //distanta pana la vecin este distanta pana la elem. curent + 1
lin[sf] = l; //punem vecinul i in coada
col[sf] = c;
sf++;
}
}
vf++;
}

// afisarea solutiei : aifsam toate distantele: dist[i][j] = distanta de la a[L][C] la a[i][j]
//am marcat cu x casutele obstacol.
for (i = 1; i <= n ; ++i) {
for (j = 1; j <= m ; ++j) {
if (dist[i][j] == -1) {
printf("x ");
}
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
*/

</syntaxhighlight>

== [http://varena.ro/problema/alee alee] ==
<syntaxhighlight>
#include <stdio.h>

#define MAX_N 175

int a[MAX_N + 2][MAX_N + 2];

int dx[] = { 1, -1, 0, 0, };
int dy[] = { 0, 0, 1, -1, };

//coada in care punem coordonatele catutelor parcurse
int l[MAX_N * MAX_N];
int c[MAX_N * MAX_N];

int main() {
FILE *fin = fopen( "alee.in", "r" );
FILE *fout = fopen( "alee.out", "w" );
int n, m, i, j, in, sf;
int x, y, L1, C1, L2, C2;;

fscanf(fin, "%d %d", &n, &m); // n - dim matricei, m - nr de copaci
for (i = 0; i < m; i++) { // citim coordonatele celor m copaci
fscanf( fin, "%d %d", &x, &y);
a[x][y] = 1; // marcam in matrice copacul cu 1
}

fscanf( fin, "%d %d", &L1, &C1); //coordonatele portii de intrare
fscanf( fin, "%d %d", &L2, &C2); //coordonatele portii de iesire

//Bordarea matricei patratice
for ( i = 0; i <= n + 1; i++ )
a[0][i] = a[n + 1][i] =a[i][0] = a[i][n + 1] = 1;

//BFS
a[L1][C1] = 1; // punem in matrice dimensiunea aleii de la poarta de intrare la ea insasi
l[0] = L1; // punem ca prim element in coada, coordonatele portii de intrare
c[0] = C1;
sf = 1; // sfarsitul cozii; avem in coada un singur element
in = 0; // pozitia elementuluu din coada curent.
while ( in < sf && a[L2][C2] == 0 ) {// cata vreme mai am elemente in coada si cata vreme nu am calculat drumul pana la poarta de iesire
for ( i = 0; i < 4; i++ ){ // parcugem toti vecinii
x = l[in] + dx[i]; // calculam linia si coloana vecinului
y = c[in] + dy[i];
if ( a[x][y] == 0 ) { // daca nu am copac si inca nu am calculat distanta pana aici
a[x][y] = a[l[in]][c[in]] + 1; // lungimea pana aici e lungimea casutei prin care am ajuns + 1
l[sf] = x; // punem coordonatele casutei in coada
c[sf] = y;
sf ++; // crestem dimenziunea cozii
}
}
in ++; // trecem la urmatorul element de analizat din coada
}

// afisarea solutiei
fprintf(fout, "%d\n", a[L2][C2]);
return 0;
}
</syntaxhighlight>

= Tema =
* [http://varena.ro/problema/panda panda]
* [http://varena.ro/problema/insule insule]

10 2018 Lectia17 - Revision history

Bella: /* Tema */