Question

Scrieti un program care citeste un tablou bidimensional cu m linii si n coloane(m,n<=30) care memoreaza valori egale cu 1 sau 0. Sa se afiseze perechile de linii care memoreaza aceleasi valori, nu obligatoriu in aceeasi ordine.
ex: m=5, n=3
1 1 0
1 0 1
0 0 1
0 1 1
1 0 0
se afiseaza: (1,2), (1,4), (2,4), (3,5)

Answer 1

Folosim un singur vector de frecventa si nu ne trebuie nici sa memoram matricea.

#include <iostream>

using namespace std;

int m,n,x,v[60];

int main()
{

    cin >> m >> n;

    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        {
            cin >> x;
            if(x)
                v[2*i+1]++;
            else
                v[2*i]++;
        }

    int ok=0;

    for(int i=0;i<m-1;i++)
        for(int j=i+1;j<m;j++)
            if(v[2*i]==v[2*j] and v[2*i+1]==v[2*j+1])
            {
                if(ok) cout << ", ";
                cout << "(" << i+1 << "," << j+1 << ")";
                ok=1;
            }

    return 0;

}

Acum, intrebarea, de ce aceast program lucreaza si ce el face?
Noi trebuie sa gasim asa linii astfel incit numarul de zerouri de pe prima linie sa fie egal cu numarul de zerouri de pe a doua linie si numarul de cifre de unu de pe prima linie sa fie egal cu numarul de cifre de unu de pe a doua linie.
Daca atragem atentia pe m linii pot exista maximum 60 valori distincte, deoarece m<=30 si exista posibilitatea de a alege intre 1 si 0, deci 30*2=60.
Initializam un vector v[60], la inceput gol.
Acest vector ne va indica cite elemente de zero si cite de unu sint pe o linie.
La citirea tabloului, daca am dat de zero atunci pozitia para 2*i, unde i-numarul liniei se mareste (vectorul initial avind toate elementele 0), iar daca am dat de unu atunci pozitia impara 2*i+1 se mareste.
Deci am construit acest vector si pentru maxima eficienta il construim la citirea tabloului.
Dupa nu avem ce face, decit sa parcurgem de la 1 linie la m linie, 2 linie la m linie, 3 linie la m linie... sa controlam daca numerele de zerouri si de unu sunt egale pe amindoua linii, si daca sunt afisam frumos prin paranteze cum e indicat in exemplu.
Pentru frumusete ca sa nu puna mereu virgula dupa ultimul element, initializam variabila ok. Idea este usoara, vom pune virgula mereu inaintea afisarii unui punct, iar pentru a nu afisa inainte de primul punct folosim variabila ok.