Задача

Задана матрица [latex]K[/latex], содержащая [latex]n[/latex] строк и [latex]m[/latex] столбцов. Седловой точкой этой матрицы назовём элемент, который одновременно является минимумом в своей строке и максимумом в своём столбце.
Найдите количество седловых точек заданной матрицы.

Входные данные

Первая строка содержит целые числа [latex]n[/latex] и [latex]m[/latex]. [latex](1 ≤ n, m ≤ 750)[/latex]. Далее следуют [latex]n[/latex] строк по [latex]m[/latex] чисел в каждой. [latex]j[/latex]-ое число [latex]i[/latex]-ой строки равно [latex]k_{ij}[/latex]. Все [latex]k_{ij}[/latex] по модулю не превосходят [latex]1000[/latex].

Выходные данные

Выведите количество седловых точек.

Тесты

#	Входные данные	Выходные данные
1	2 2 0 0 0 0	4
2	3 3 1 2 3 4 3 6 9 5 3	0
3	4 4 1 2 0 0 2 2 4 4 0 0 1 1 3 4 2 1	0
4	2 2 3 2 1 1	1

Код программы

#include <iostream>
#define Unknown 1001
using namespace std;

int main() {
    int n, m,uf = 0,maxi;
    //input
    cin >> n >> m;
    int ** x = new int * [n];
    for (int i = 0; i < n; i++)
        x[i] = new int[m];
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            cin >> x[i][j];
    //workspace
    int  max[m];
    for (int i = 0; i < m; i++){
        max[i] = Unknown;   
    }
    for (int i = 0; i < n; i++) {
        int min = x[i][0];
        for (int j = 1; j < m; j++) {
            if ( min > x[i][j] ) {
                min = x[i][j];
            }
        }
        for (int j = 0; j < m; j++) {
            if (x[i][j] == min) {
                if (max[j] != Unknown){
                    maxi = max[j];  
                }
                else {
                    maxi = x[i][j];
                    for (int l = 0; l < n; l++) {
                        if (maxi < x[l][j]){
                            maxi = x[l][j];
                        }
                    }
                    max[j] = maxi;
                }
                if ( maxi == min) {
                    uf++;
                }
            }
        }
    }
    //output
    cout << uf;
    return 0;
}

#include <iostream>

#define Unknown 1001

using namespace std;

int main() {

int n, m,uf = 0,maxi;

//input

cin >> n >> m;

int ** x = new int * [n];

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

x[i] = new int[m];

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

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

cin >> x[i][j];

//workspace

int max[m];

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

max[i] = Unknown;

}

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

int min = x[i][0];

for (int j = 1; j < m; j++) {

if ( min > x[i][j] ) {

min = x[i][j];

}

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

if (x[i][j] == min) {

if (max[j] != Unknown){

maxi = max[j];

}

else {

maxi = x[i][j];

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

if (maxi < x[l][j]){

maxi = x[l][j];

}

max[j] = maxi;

}

if ( maxi == min) {

uf++;

}

//output

cout << uf;

return 0;

}

Решение задачи

Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!