Clasele 9-10 lecția 7 - 13 nov 2015

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:

• 1033 - Labyrinth (Timus);
• 1709 - Penguin-Avia (Timus);
• 1242 - Werewolf (Timus);
• 1218 - Episode N-th: The Jedi Tournament (Timus);
• 1080 - Map Coloring (Timus).