e-olymp 5282. Седловые точки

Задача

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

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

Первая строка содержит целые числа [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

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

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

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

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

Related Images:

7 thoughts on “e-olymp 5282. Седловые точки

  1. Видите, что бывает если несколько месяцев не учиться?
    — Отступы!
    — Вычислительная сложность Вашего решения $O\left(n^2m\right)$ вместо логичных $O\left(nm\right).$ Это слишком много. Причиной является то, что Вы заново пересчитываете минимумы в одной и той же строке для каждого элемента. Зачем? Их же можно запомнить в массиве.

    • Простите, а под «запомнить в массиве» вы имеете ввиду создать новый одномерный массив, в котором мы будем запоминать номера всех минимумов?

    • «Число строки» не очень удачное выражение. Лучше сказать «значение очередного элемента» или просто «очередное число в строке».
    • По строке 28. Вы используете ноль в для обозначения того, что максимум еще не вычислялся. Но в условии не сказано, что все числа положительны. Сказано, что они не превышают по модулю 1000. Т.е. нужно использовать не ноль, а какое-нибудь число превышающее по модулю 1000.
    • Теперь 1001 стало «волшебным числом». Использовать разбросанный по программе числовые константы, считается плохой практикой. Лучше объявить 1001 как, например, UNKNOWN при помощи директивы препроцессора define.

Добавить комментарий