Clasa a 7-a lecția 7 - 29 oct 2015
From Algopedia
Jump to navigationJump to search
Lectie
Am dat un test de verificare ce continea o problemă care cerea drumul minim într-o matrice. Deplasarea dintr-o căsuța în cealaltă se putea realiza doar pe orizontală sau verticală. Pentru a determina dacă se putea trece dintr-o căsuță în alta trebuiau efectuate operații pe biți. De asemenea, problema cerea și reconstituirea drumului minim în mod recursiv.
Din păcate, cu aproximativ 10 minute înainte de terminarea timpului s-a întrerupt curentul în liceu iar mulți dintre voi nu au apucat să-și trimită sursele la care încă mai lucrau.
Soluțiile oficiale
Panda
#include <stdio.h>
#define MAX_N 500
#define MAX_M 500
struct Tarc {
short int l;
short int c;
};
Tarc aduna(Tarc a, Tarc b) {
Tarc t;
t.l = a.l + b.l;
t.c = a.c + b.c;
return t;
}
Tarc vecini[] = {
{ 0, 1},
{ 0, -1},
{ 1, 0},
{-1, 0},
};
int P;
int N, M, T;
int L, C, K, S;
Tarc sursa;
char areMancare[1 + MAX_N + 1][1 + MAX_M + 1];
char accesibil[1 + MAX_N + 1][1 + MAX_M + 1];
int distanta[1 + MAX_N + 1][1 + MAX_M + 1];
Tarc coada[MAX_N * MAX_M];
int inceput, sfarsit;
Tarc drumMinim[MAX_N * MAX_M];
void reconstituireDrumMinim(Tarc tarc) {
int i;
drumMinim[distanta[tarc.l][tarc.c]] = tarc;
if (distanta[tarc.l][tarc.c] > 1) {
i = -1;
Tarc tarcNou;
do {
i++;
tarcNou = aduna(tarc, vecini[i]);
} while (distanta[tarcNou.l][tarcNou.c] + 1 != distanta[tarc.l][tarc.c]);
reconstituireDrumMinim(tarcNou);
}
}
int main() {
int i, j;
FILE *in = fopen("panda.in", "r");
FILE *out = fopen("panda.out", "w");
// FILE *in = stdin;
// FILE *out = stdout;
fscanf(in, "%d", &P);
fscanf(in, "%d %d %d", &N, &M, &T);
fscanf(in, "%d %d %d %d", &L, &C, &K, &S);
sursa.l = L;
sursa.c = C;
for (i = 0; i < T; i++) {
fscanf(in, "%d %d", &L, &C);
areMancare[L][C] = 1;
}
int accesibile = 0;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
int cod;
fscanf(in, "%d", &cod);
accesibil[i][j] =
(((cod | K) & ((1 << S) - 1)) == ((1 << S) - 1)) &&
(((cod & K) & ((1 << S) - 1)) == 0);
if (!(i == sursa.l && j == sursa.c))
accesibile += accesibil[i][j];
}
}
inceput = sfarsit = 0;
coada[sfarsit] = sursa;
sfarsit++;
distanta[sursa.l][sursa.c] = 1;
while (inceput < sfarsit) {
Tarc tarc = coada[inceput];
inceput++;
for (i = 0; i < 4; i++) {
Tarc tarcNou = aduna(tarc, vecini[i]);
if (accesibil[tarcNou.l][tarcNou.c]) {
if (distanta[tarcNou.l][tarcNou.c] == 0) {
distanta[tarcNou.l][tarcNou.c] = distanta[tarc.l][tarc.c] + 1;
coada[sfarsit] = tarcNou;
sfarsit++;
}
}
}
}
int distantaMinima = 0x7fffffff;
int nrTarcuriMinime = 0;
Tarc tarcMinim;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
if (areMancare[i][j] && distanta[i][j] > 0) {
if (distantaMinima > distanta[i][j]) {
distantaMinima = distanta[i][j];
nrTarcuriMinime = 1;
tarcMinim.l = i;
tarcMinim.c = j;
} else if (distantaMinima == distanta[i][j]) {
nrTarcuriMinime++;
}
}
}
}
distantaMinima--;
//reconstituireDrumMinim(tarcMinim);
if (P == 1) {
fprintf(out, "%d\n", accesibile);
} else if (P == 2) {
fprintf(out, "%d %d\n", distantaMinima, nrTarcuriMinime);
// } else {
// for (i = 1; i <= distantaMinima + 1; i++) {
// fprintf(out, "%d %d\n", drumMinim[i].l, drumMinim[i].c);
// }
}
fclose(in);
fclose(out);
return 0;
}Pandele
#include <stdio.h>
#define MAX_N 500
#define MAX_M 500
struct Tarc {
int l;
int c;
};
Tarc aduna(Tarc a, Tarc b) {
Tarc t;
t.l = a.l + b.l;
t.c = a.c + b.c;
return t;
}
Tarc vecini[] = {
{ 0, 1},
{ 0, -1},
{ 1, 0},
{-1, 0},
};
int P;
int N, M, T;
int L, C, K, S;
Tarc sursa;
int areMancare[1 + MAX_N + 1][1 + MAX_M + 1];
int accesibil[1 + MAX_N + 1][1 + MAX_M + 1];
int distanta[1 + MAX_N + 1][1 + MAX_M + 1];
Tarc coada[MAX_N * MAX_M];
int inceput, sfarsit;
Tarc drumMinim[MAX_N * MAX_M];
void reconstituireDrumMinim(Tarc tarc) {
int i;
drumMinim[distanta[tarc.l][tarc.c]] = tarc;
if (distanta[tarc.l][tarc.c] > 1) {
i = -1;
Tarc tarcNou;
do {
i++;
tarcNou = aduna(tarc, vecini[i]);
} while (distanta[tarcNou.l][tarcNou.c] + 1 != distanta[tarc.l][tarc.c]);
reconstituireDrumMinim(tarcNou);
}
}
int main() {
int i, j;
FILE *in = fopen("pandele.in", "r");
FILE *out = fopen("pandele.out", "w");
// FILE *in = stdin;
// FILE *out = stdout;
fscanf(in, "%d", &P);
fscanf(in, "%d %d %d", &N, &M, &T);
fscanf(in, "%d %d %d %d", &L, &C, &K, &S);
sursa.l = L;
sursa.c = C;
for (i = 0; i < T; i++) {
fscanf(in, "%d %d", &L, &C);
areMancare[L][C] = 1;
}
int accesibile = 0;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
int cod;
fscanf(in, "%d", &cod);
accesibil[i][j] =
(((cod | K) & ((1 << S) - 1)) == ((1 << S) - 1)) &&
(((cod & K) & ((1 << S) - 1)) == 0);
if (!(i == sursa.l && j == sursa.c))
accesibile += accesibil[i][j];
}
}
inceput = sfarsit = 0;
coada[sfarsit] = sursa;
sfarsit++;
distanta[sursa.l][sursa.c] = 1;
while (inceput < sfarsit) {
Tarc tarc = coada[inceput];
inceput++;
for (i = 0; i < 4; i++) {
Tarc tarcNou = aduna(tarc, vecini[i]);
if (accesibil[tarcNou.l][tarcNou.c]) {
if (distanta[tarcNou.l][tarcNou.c] == 0) {
distanta[tarcNou.l][tarcNou.c] = distanta[tarc.l][tarc.c] + 1;
coada[sfarsit] = tarcNou;
sfarsit++;
}
}
}
}
int distantaMinima = 0x7fffffff;
int nrTarcuriMinime = 0;
Tarc tarcMinim;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
if (areMancare[i][j] && distanta[i][j] > 0) {
if (distantaMinima > distanta[i][j]) {
distantaMinima = distanta[i][j];
nrTarcuriMinime = 1;
tarcMinim.l = i;
tarcMinim.c = j;
} else if (distantaMinima == distanta[i][j]) {
nrTarcuriMinime++;
}
}
}
}
distantaMinima--;
reconstituireDrumMinim(tarcMinim);
// if (P == 1) {
// fprintf(out, "%d\n", accesibile);
// } else if (P == 2) {
// fprintf(out, "%d %d\n", distantaMinima, nrTarcuriMinime);
// } else {
for (i = 1; i <= distantaMinima + 1; i++) {
fprintf(out, "%d %d\n", drumMinim[i].l, drumMinim[i].c);
}
// }
fclose(in);
fclose(out);
return 0;
}Temă
Pentru data viitoare veți avea de rezolvat ca temă problema dată la test în cele două forme ale sale:
