Rezolvare #1507 grupuri de pe PbInfo.ro

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

grupuri.out

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)}

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema grupuri:

#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("grupuri.in");
ofstream fout("grupuri.out");

int tabla[105][105], n, grupuri;

void rezolvare(int linie, int coloana) {
    if(1 <= linie && linie <= n && 1 <= coloana && coloana <= n) {
        if(tabla[linie][coloana] == 1) {
            tabla[linie][coloana] = 0;

            rezolvare(linie, coloana + 1);
            rezolvare(linie, coloana - 1);
            rezolvare(linie + 1, coloana);
            rezolvare(linie - 1, coloana);
        }
    }
}

int main() {

    fin >> n;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            fin >> tabla[i][j];
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(tabla[i][j]) {
                grupuri++;
                rezolvare(i, j);
            }
        }
    }

    fout << grupuri;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1507 grupuri

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1507 grupuri de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1507 grupuri