Clasele 9-10 lecția 7 - 13 nov 2015
From Algopedia
1033 - Labyrinth
#include <cstdio>
#include <queue>
using std::queue;
const int MAX_N = 33;
int N;
char harta[1 + MAX_N + 1][1 + MAX_N + 1];
// . - spațiu liber
// # - zid
// ! - spațiu liber parcurs (accesibil)
struct Casuta {
int l;
int c;
Casuta add(const Casuta &alta) const {
Casuta rezultat;
rezultat.l = this->l + alta.l;
rezultat.c = this->c + alta.c;
return rezultat;
}
};
Casuta vecini[] = {
{-1, 0},
{ 0, 1},
{ 1, 0},
{ 0,-1},
};
queue<Casuta> coadaBfs;
int raspuns;
int main(void) {
int i, j, k;
// citirea datelor
scanf("%d", &N);
for (i = 1; i <= N; ++i) {
scanf("\n");
for (j = 1; j <= N; ++j) {
scanf("%c", &harta[i][j]);
}
}
for (i = 0; i <= N + 1; i++) {
harta[0][i] = '#';
harta[N + 1][i] = '#';
harta[i][0] = '#';
harta[i][N + 1] = '#';
}
coadaBfs.push({1, 1});
coadaBfs.push({N, N});
harta[1][1] = '!';
harta[N][N] = '!';
while (!coadaBfs.empty()) {
Casuta nod = coadaBfs.front();
coadaBfs.pop();
for (i = 0; i < 4; ++i) {
Casuta vecin;
vecin = nod.add(vecini[i]);
if (harta[vecin.l][vecin.c] == '.') {
harta[vecin.l][vecin.c] = '!';
coadaBfs.push(vecin);
}
}
}
raspuns = 0;
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
if (harta[i][j] == '!') {
Casuta nod = {i, j};
for (k = 0; k < 4; ++k) {
Casuta vecin = nod.add(vecini[k]);
if (harta[vecin.l][vecin.c] == '#') {
raspuns++;
}
}
}
}
}
raspuns -= 4; // scădem pereții intrărilor
raspuns *= 9; // înmulțim cu aria unui perete
printf("%d\n", raspuns);
return 0;
}
1709 - Penguin-Avia
#include <cstdio>
#include <queue>
using std::queue;
const int MAX_N = 100;
int N;
int D, A;
char adiacenta[MAX_N][MAX_N];
queue<int> coadaBfs;
bool vizitat[MAX_N];
long long raspuns;
int main(void) {
int i, j;
// citirea datelor
scanf("%d", &N);
scanf("%d %d", &D, &A);
for (i = 0; i < N; ++i) {
scanf("\n");
for (j = 0; j < N; ++j) {
scanf("%c", &adiacenta[i][j]);
}
}
for (i = 0; i < N; i++) {
if (!vizitat[i]) {
if (i != 0) {
adiacenta[0][i] = 'a';
adiacenta[i][0] = 'a';
raspuns += A;
}
coadaBfs.push(i);
vizitat[i] = true;
while (!coadaBfs.empty()) {
int nod = coadaBfs.front();
coadaBfs.pop();
int vecin;
for (vecin = 0; vecin < N; vecin++) {
if (adiacenta[nod][vecin] == '1') {
if (!vizitat[vecin]) {
adiacenta[nod][vecin] = '0';
adiacenta[vecin][nod] = '0';
vizitat[vecin] = true;
coadaBfs.push(vecin);
} else {
adiacenta[nod][vecin] = 'd';
adiacenta[vecin][nod] = 'd';
raspuns += D;
}
}
}
}
}
}
printf("%lld\n", raspuns);
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
printf("%c", adiacenta[i][j]);
}
printf("\n");
}
return 0;
}
Temă
Pentru data viitoare veți avea de rezolvat următoarele 5 probleme: