Clasa a X-a · Tablouri bidimensionale (matrice)Read in English

Punct șa în C++

În engleză: Saddle point

O(n²)C++1766 de linii2 exemple

Ideea

Un punct șa este un element care este minim pe linia lui și maxim pe coloana lui. Pentru fiecare element a[i][j] verificăm cele două condiții cu două funcții separate. Se afișează linia, coloana și valoarea fiecărui punct șa, sau NU EXISTA dacă nu există niciunul.

Descrierea în engleză

A saddle point is an element that is the minimum of its row and the maximum of its column. For every element a[i][j] we check the two conditions with two separate functions. The row, column and value of every saddle point are printed, or NU EXISTA (none) if there is none.

Complexitate
O(n * m * (n + m))
Clasa
Clasa a X-a (Grade 10)

Exemple

Exemplul 1

Intrare

3 3
3 5 7
2 1 4
6 8 9

Ieșire așteptată

3 1 6
Exemplul 2

Intrare

2 2
1 2
2 1

Ieșire așteptată

NU EXISTA

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

punct-sa.cpp
/*
 * Titlu: Punct șa
 * Clasa: 10
 * Capitol: Tablouri bidimensionale (matrice)
 * Descriere: Un punct șa este un element care este minim pe linia lui și maxim pe
 *            coloana lui. Pentru fiecare element a[i][j] verificăm cele două
 *            condiții cu două funcții separate. Se afișează linia, coloana și
 *            valoarea fiecărui punct șa, sau NU EXISTA dacă nu există niciunul.
 * Complexitate: O(n * m * (n + m))
 *
 * Exemplu
 * Intrare:
 * 3 3
 * 3 5 7
 * 2 1 4
 * 6 8 9
 * Ieșire: 3 1 6
 *
 * Exemplu
 * Intrare:
 * 2 2
 * 1 2
 * 2 1
 * Ieșire: NU EXISTA
 */
#include <iostream>
using namespace std;

int a[101][101], n, m;

bool minimPeLinie(int i, int j)
{
    for (int k = 1; k <= m; k++)
        if (a[i][k] < a[i][j])
            return false;
    return true;
}

bool maximPeColoana(int i, int j)
{
    for (int k = 1; k <= n; k++)
        if (a[k][j] > a[i][j])
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    bool gasit = false;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (minimPeLinie(i, j) && maximPeColoana(i, j))
            {
                cout << i << ' ' << j << ' ' << a[i][j] << '\n';
                gasit = true;
            }
    if (!gasit)
        cout << "NU EXISTA\n";
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.