Седловые точки

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

Найдите количество седловых точек заданной матрицы.

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

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

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

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

Алгоритм решения задачи

  • Для каждого столбца вычисляем максимальное значение;
  • Для каждой строки вычисляем минимальное значение;
  • Сравниваем элементы матрицы со значениями максимума и минимума.

Решение

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var parts = Console.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        var n = Convert.ToInt32(parts[0]);
        var m = Convert.ToInt32(parts[1]);

        var matrix = new int[n, m];

        var rowMin = new int[n];
        var colMax = new int[m];

        for (int i = 0; i < n; i++)
        {
            var row = Array.ConvertAll(Console.ReadLine().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries), x => int.Parse(x));
            rowMin[i] = row.Min();
            for (int j = 0; j < m; j++)
            {
                if (i == 0)
                {
                    colMax[j] = row[j];
                }
                else if (colMax[j] < row[j])
                {
                    colMax[j] = row[j];
                }

                matrix[i, j] = row[j];
            }
        }

        var count = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (matrix[i, j] == colMax[j] && matrix[i, j] == rowMin[i])
                {
                    count++;
                }
            }
        }

        Console.WriteLine(count);
    }
}

Смотрите также: