Puncte șa într-o matrice: minim pe linie, maxim pe coloană

În această problemă, un punct șa este o celulă care are valoare minimă pe linia sa și maximă pe coloana sa. Ambele condiții trebuie îndeplinite de aceeași celulă. Alte enunțuri pot inversa minimul și maximul, deci citește definiția înainte de a reutiliza codul.

Un exemplu cu două condiții simultane

Pentru liniile 3 4 și 1 2, minimul primei linii este 3. Pe prima coloană, maximul este tot 3, deci celula (1,1), cu numerotare de la 1, este punct șa. Valoarea 1 este minimă pe a doua linie, dar nu este maximă pe coloană.

Citim 1≤n,m≤100 și n·m întregi. Afișăm numărul punctelor șa, apoi coordonatele lor, câte o pereche pe linie, în ordinea parcurgerii pe linii. Egalitățile sunt acceptate: într-o matrice cu toate valorile egale, fiecare celulă este punct șa după definiția noastră.

Calculăm extremele o singură dată

Un tablou minLin păstrează minimul fiecărei linii, iar maxCol maximul fiecărei coloane. Inițializăm fiecare extremă cu un element real din linia sau coloana respectivă. Zero nu este o inițializare generală corectă pentru date negative sau pozitive arbitrare.

După aceste două parcurgeri, verificăm fiecare celulă prin două egalități. Nu mai reparcurgem întreaga linie și coloană pentru fiecare candidat. Indicii interni sunt de la zero, iar la afișare adăugăm unu.

În matricea 3,4 / 1,2, valoarea 3 este minim pe linia sa și maxim pe coloana sa. Indicii interni sunt (0,0), iar coordonatele afișate de program sunt 1 1.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int a[100][100],minLin[100],maxCol[100];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    for(int i=0;i<n;++i) {
        minLin[i]=a[i][0];
        for(int j=1;j<m;++j) if(a[i][j]<minLin[i]) minLin[i]=a[i][j];
    }
    for(int j=0;j<m;++j) {
        maxCol[j]=a[0][j];
        for(int i=1;i<n;++i) if(a[i][j]>maxCol[j]) maxCol[j]=a[i][j];
    }
    int cate=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j)
        if(a[i][j]==minLin[i] && a[i][j]==maxCol[j]) ++cate;
    cout << cate << '\n';
    for(int i=0;i<n;++i) for(int j=0;j<m;++j)
        if(a[i][j]==minLin[i] && a[i][j]==maxCol[j]) cout << i+1 << ' ' << j+1 << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n,vector<int>(m));
    vector<int> minLin(n),maxCol(m);
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    for(int i=0;i<n;++i) {
        minLin[i]=a[i][0];
        for(int j=1;j<m;++j) if(a[i][j]<minLin[i]) minLin[i]=a[i][j];
    }
    for(int j=0;j<m;++j) {
        maxCol[j]=a[0][j];
        for(int i=1;i<n;++i) if(a[i][j]>maxCol[j]) maxCol[j]=a[i][j];
    }
    int cate=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j)
        if(a[i][j]==minLin[i] && a[i][j]==maxCol[j]) ++cate;
    cout << cate << '\n';
    for(int i=0;i<n;++i) for(int j=0;j<m;++j)
        if(a[i][j]==minLin[i] && a[i][j]==maxCol[j]) cout << i+1 << ' ' << j+1 << '\n';
}

Cost și cazuri cu egalități

Calcularea extremelor, numărarea și afișarea sunt câteva parcurgeri complete ale aceleiași matrice. Timpul total este O(n·m). Tablourile de extreme folosesc O(n+m) memorie suplimentară, pe lângă matricea de O(n·m) elemente.

Nu alegem o singură poziție pentru fiecare minim. Dacă minimul apare de mai multe ori pe o linie, fiecare celulă poate îndeplini și condiția de coloană. Păstrarea doar a primei poziții ar pierde rezultate valide.

Exersează

Matricea 3 4 / 1 2 are un singur punct șa, (1,1). Matricea 1 2 / 2 1 nu are niciunul. Într-o matrice 2×2 plină cu 7, sunt patru. Verifică și o singură celulă: ea este simultan minim pe linie și maxim pe coloană.

Continuă cu maxime și minime, matrice și tablouri auxiliare.

Întrebări frecvente

Ce este un punct șa într-o matrice?

În definiția acestei lecții, este o celulă minimă pe linia sa și maximă pe coloana sa. Unele enunțuri inversează rolurile, deci definiția trebuie citită înainte de aplicarea algoritmului.

Pot exista mai multe puncte șa?

Da. Egalitățile pot face ca mai multe celule să îndeplinească ambele condiții. Nu opri căutarea după prima celulă dacă cerința solicită toate pozițiile.

Cum verific eficient condiția de punct șa?

Precalculează minimul fiecărei linii și maximul fiecărei coloane. O celulă este eligibilă când valoarea ei este egală cu ambele rezultate corespunzătoare.