👤
ANDRADA1212ID
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 :

CINEVAFARANUMEID

#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 pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari