Clasa a 7-a lecția 6 - 22 oct 2015
From Algopedia
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ă
Pentru data viitoare veți avea de rezolvat următoarele probleme:
Rezolvări aici [2]