👤
Alexlolshockp1aywd
a fost răspuns

Cerința
Scrieţi un program care citeşte din fişierul de intrare un număr natural n şi o matrice pătratică A de dimensiune n x n, 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 şi |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 afişează în fişierul de ieşire numărul de grupuri conţinute de matrice.

Date de intrare
Fișierul de intrare grupuri.in conține pe prima linie numărul n, iar pe următoarele n linii câte n numere naturale 0 sau 1, reprezentând elementele matricei A.

Date de ieșire
Fișierul de ieșire grupuri.out va conține pe prima linie numărul de grupuri prezente în matricea din fişierul de intrare.

Restricții și precizări
2 ≤ n ≤ 100
Exemplu:
grupuri.in

4
1 0 0 1
0 0 1 1
0 1 0 1
1 1 0 0
grupuri.out

3
Explicație
Cele trei grupuri din fişierul de intrare sunt (considerând matricea indexată de la 1 la n):
G1 = {(1, 1)}
G2 = {(1, 4), (2, 3), (2, 4), (3, 4)}
G3 = {(3, 2), (4, 1), (4, 2)}

Răspuns :

Andreidiaconescu18

Ti-am facut cu citire de la tastatura si scriere la consola. Adaptezi tu pentru fisier.


#include <iostream>

#include <stack>

using namespace std;

struct punct{

   int i,j;

};

int main() {

   int n;

   int a[100][100];

   stack<punct> stiva;

   cout << "n=";

   cin >> n;

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

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

           cout << "a[" << i << "][" << j << "]=";

           cin >> a[i][j];

       }

   cout << "Matricea initiala:" << endl;

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

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

           cout << a[i][j] << " ";

       cout << endl;

   }

   int k=2;

   bool sem=true;

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

       for(int j=0; j<n && sem; j++)

           if(a[i][j]==1)

           {

               struct punct p;

               p.i=i;

               p.j=j;

               stiva.push(p);

               cout<<"!!!"<<i<<" "<<j<<endl;

               sem= false;

           }

   sem=true;

   while(sem)

   {

       sem = false;

       while(!stiva.empty())

       {

           struct punct p = stiva.top();

           a[p.i][p.j]=k;

           struct punct p2;

           stiva.pop();

           if(p.i>=0 && p.i<n && p.j>=0 && p.j<n)

           {

               if(a[p.i][p.j+1]==1 && p.j+1<n)

               {

                   a[p.i][p.j+1] = k;

                   p2.i=p.i;

                   p2.j=p.j+1;

                   stiva.push(p2);

               }

               if(a[p.i][p.j-1]==1 && p.j-1>=0)

               {

                   a[p.i][p.j-1] = k;

                   p2.i=p.i;

                   p2.j=p.j-1;

                   stiva.push(p2);

               }

               if(a[p.i+1][p.j]==1 && p.i+1<n)

               {

                   a[p.i+1][p.j] =k;

                   p2.i=p.i+1;

                   p2.j=p.j;

                   stiva.push(p2);

               }

               if(a[p.i-1][p.j]==1 && p.i-1>=0)

               {

                   a[p.i-1][p.j] =k;

                   p2.i=p.i-1;

                   p2.j=p.j;

                   stiva.push(p2);

               }

           }

       }

       bool sem2=true;

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

           for(int j=0; j<n && sem2; j++)

               if(a[i][j]==1)

               {

                   struct punct p;

                   p.i=i;

                   p.j=j;

                   stiva.push(p);

                   sem2 = false;

                   sem = true;

                   k++;

               }

   }

   cout << "Matricea finala:" << endl;

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

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

           cout << a[i][j] << " ";

       cout << endl;

   }

   cout<<"Numarul de grupuri este: "<<k-1<<endl;

   return 0;

}


Alte intrebari