Задача
Задана матрица [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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
/* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Main { public static int Unknown = 1001; public static void main (String[] args) throws java.lang.Exception { int n, m,uf = 0,maxi; //input Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); int [][] x = new int[n][m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) x[i][j] = in.nextInt(); //workspace int[] max = new int[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 System.out.print(uf); } } |
Решение задачи
Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!
Ссылки
Условие задачи на e-olymp.com.
Код решения на ideone.com.