Question

Buna ziua, am nevoie de idei, sau daca se poate chiar codul rezolvat ( c++ ). Va rog mult!

Answer 1

► Cerinta :

Pe o foaie de hartie este desenata o plasa cu N coloane si M randuri. In interiorul plasei sunt desenate B figuri. Fiecare figura consta din una sua mai multe celule intregi. Figurile nu se suprapun, nu au laturi sau varfuri comune. De determinat celula cu suprafata maxima.

► Program C++ :

#include <iostream>

#include <fstream>

using namespace std;

int M, N;

bool mat[101][101];

int expandeaza(int x, int y) {

int s = 1;

//Marcheaza pozitia curenta ca inactiva

mat[x][y] = 0;

//Aduna suprafetele blocurilor adiactente active

if (x > 0 && mat[x - 1][y])

 s += expandeaza(x - 1, y);

if (y > 0 && mat[x][y - 1])

 s += expandeaza(x, y - 1);

if (x < (N - 1) && mat[x + 1][y])

 s += expandeaza(x + 1, y);

if (y < (M - 1) && mat[x][y + 1])

 s += expandeaza(x, y + 1);

//Returneaza suprafata gasita

return s;

}

int main() {

//Citire date

ifstream f("pr3_in.txt");

f >> N >> M;

for (int i = 1; i <= M; i++)

 for (int j = 1; j <= N; j++)

  f >> mat[i][j];

f.close();

//Gaseste suprafata maxima

int smax = 0;

int imax =0, jmax = 0;

for (int i = 1; i <= M; i++) {

 for (int j = 1; j <= N; j++) {

  if (mat[i][j] == 1) {

   int scurent = expandeaza(i, j);

   if (scurent > smax) {

    smax = scurent;

    imax = i;

    jmax = j;

   }

  }

 }

}

//Afisare rezultat

ofstream g("pr3_out.txt");

g << smax << endl << imax << " " << jmax;

g.close();

}

► Nota :

Folosirea variabilelor globale nu este recomandata in practica dar e folosita aici pentru a simplifica codul.

Programul se foloseste de recursivitate pentru a determina suprafata unei figuri, expandand de fiecare data la celulele vecine care contin valoarea 1.