10 2018 Lectia17

BFS ( Algoritmul lui Lee )

/*
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
 */

alee

#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;
}

Tema

• panda
• insule