👤
ANDRADA1212WIX
a fost răspuns

Scrieți un program care citește de la tastatură un număr natural n și o matrice pătratică A de dimensiuni nxn, elementele acesteia putând avea doar valorile 0 sau 1. Două elemente A(i1, j1) și A(i2, j2) sunt adiacente dacă sunt „vecine” pe o aceeași linie sau coloană: (i1=i2 și |j1-j2|=1) sau (j1=j2 sau |i1-i2|=1). Un grup reprezintă fie un singur element al matricii având valoarea 1, neadiacent cu niciun alt element cu valoarea 1, fie o mulțime de elemente având valoarea 1, fiecare dintre ele fiind adiacent cu cel puțin un alt element din mulțimea respectivă și neadiacent cu niciun alt element din alt grup. Programul trebuie să afișeze pe ecran numărul de grupuri conținute de matrice și coordonatele elementelor acestora.

Exemplu: Numărul de grupe din matricea 4x4 de mai jos este 3 iar cele trei grupuri sunt: G1={(0,0)}, G2={(0,3),(1,2),(1,3),(2,3)}, G3={(2,1),(3,0),(3,1)}.

1 0 0 1
0 0 1 1
0 1 0 1
1 1 0 0

Răspuns :

CINEVAFARANUMEWIX

#include <iostream>

using namespace std;

bool A[1000][1000];

int grupe[1000][1000];

int k = 0;

int n;

bool existagrupa[100000];

void setall(int i, int old_val, int new_val){

   for(int j = 0; j <= i; j++)

       for(int l = 0; l < n; l++)

           if(grupe[j][l] == old_val)

               grupe[j][l] = new_val;

   existagrupa[old_val] = false;

}

void afisareCoordonate_recursiv(int val, int b_x, int b_y){

   if(grupe[b_x][b_y] == val){

       cout << b_x << ',' << b_y << '\n';

       grupe[b_x][b_y] = 0;

       if(b_y < n-1)

           afisareCoordonate_recursiv(val, b_x, b_y+1);

       if(b_y > 0)

           afisareCoordonate_recursiv(val, b_x, b_y-1);

       if(b_x < n-1)

           afisareCoordonate_recursiv(val, b_x+1, b_y);

       if(b_x > 0)

           afisareCoordonate_recursiv(val, b_x-1, b_y);

   }

}

void afisareCoordonate(int val){

   for(int i = 0; i < n; i++)

   for(int j = 0; j < n; j++){

       if(grupe[i][j] == val){

           afisareCoordonate_recursiv(val, i, j);

           return;

       }

   }

}

int main(){

   cin >> n;

   for(int i = 0; i < n; i++)

       for(int j = 0; j < n; j++){

           cin >> A[i][j];

           if(A[i][j]){

               if(i > 0){

                   if(A[i-1][j])

                       grupe[i][j] = grupe[i-1][j];

                   else if(A[i][j-1])

                       grupe[i][j] = grupe[i][j-1];

                   else grupe[i][j] = ++k;

                   if(A[i][j-1] && grupe[i][j-1] != grupe[i][j])

                       setall(i, grupe[i][j-1], grupe[i][j]);

               }else {

                   if(A[0][j-1])

                       grupe[0][j] = grupe[0][j-1];

                   else grupe[0][j] = ++k;

               }

               existagrupa[grupe[i][j]] = true;

           }

       }

   int grupa_ = 0, totalgrupe = 0;

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

       if(existagrupa[i])

           totalgrupe++;

   }

   cout << totalgrupe << '\n';

   for(int i = 1; i <= k && grupa_ < totalgrupe; i++){

       if(existagrupa[i]){

           cout << "Grupa " << ++grupa_ << '\n';

           afisareCoordonate(i);

       }

   }

}

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că informațiile disponibile v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de sprijin, nu ezitați să ne contactați. Vă așteptăm cu drag și data viitoare! Nu uitați să adăugați site-ul nostru la favorite pentru acces rapid.


Wix Learning: Alte intrebari