Clasa a 7-a lecția 6 - 22 oct 2015

From Algopedia
Jump to navigationJump to search

Tema Rezolvări

Rezolvări aici [1]

Problema Alee

Cu reconstituirea drumului

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

Cu operații specifice structurii coadă

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

Cu coadă implementată circular

...

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

...

Temă

Tema 6 clasa a 7-a

Pentru data viitoare veți avea de rezolvat următoarele probleme:

Rezolvări aici [2]