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

 

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

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

 

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

 

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

 

Пример входа 1

Пример выхода 1

2 2

0 0

0 0

4

 

 

Пример входа 2

Пример выхода 2

3 4

7 1 5 3

3 2 6 4

5 2 8 6

2

 

 

РЕШЕНИЕ

массивы

 

Анализ алгоритма

Пусть minRow – массив, в котором minRow[i] содержит минимальное значение i-ой строки.

Пусть maxCol – массив, в котором maxCol[i] содержит максимальное значение i-го столбца.

Число седловых точек равно такому количеству Aij, для которых Aij = minRow[i] и Aij = maxCol[j].

 

Пример

Рассмотрим второй пример. Он содержит 2 седловые точки.

 

Реализация алгоритма

Входную матрицу храним в двумерном целочисленном массиве а. Объявим массивы minRow и maxCol.

 

#define MAX 800

int a[MAX][MAX];

int minRow[MAX], maxCol[MAX];

 

Читаем входную матрицу.

 

scanf("%d %d",&n,&m);

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

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

  scanf("%d",&a[i][j]);   

 

Для каждой i-ой строки вычисляем наименьший элемент и сохраняем его в minRow[i].

 

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

{

  minRow[i] = 1000;

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

    if(a[i][j] < minRow[i]) minRow[i] = a[i][j];

}

 

Для каждого j-го столбца вычисляем наибольший элемент и сохраняем его в maxCol[j].

 

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

{

  maxCol[j] = -1000;

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

    if(a[i][j] > maxCol[j]) maxCol[j] = a[i][j];

}

 

В переменной res подсчитываем количество aij, для которых aij = minRow[i] и aij = maxCol[j].

 

res = 0;

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

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

  if ((a[i][j] == minRow[i]) && (a[i][j] == maxCol[j])) res++;

 

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

 

printf("%d\n",res);

 

Реализация алгоритма – двойной указатель

 

#include <stdio.h>

#define MAX 800

 

int n, m, i, j, res;

int *minRow, *maxCol;

int **a;

 

int main(void)

{

  scanf("%d %d", &n, &m);

  a = new int*[n];

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

  {

    a[i] = new int[m];

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

      scanf("%d", &a[i][j]);

  }

 

  minRow = new int[n];

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

  {

    minRow[i] = 1000;

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

      if (a[i][j] < minRow[i]) minRow[i] = a[i][j];

  }

 

  maxCol = new int[m];

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

  {

    maxCol[j] = -1000;

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

      if (a[i][j] > maxCol[j]) maxCol[j] = a[i][j];

  }

 

  res = 0;

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

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

    if ((a[i][j] == minRow[i]) && (a[i][j] == maxCol[j])) res++;

 

  printf("%d\n", res);

 

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

    delete[] a[i];

  delete[] a;

  delete[] minRow;

  delete[] maxCol;

 

  return 0;

}

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static void main(String []args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int m = con.nextInt();

     

    int a[][] = new int[n][m];

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

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

      a[i][j] = con.nextInt();

 

    int minRow[] = new int[n];

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

    {

      minRow[i] = 1000;

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

        if(a[i][j] < minRow[i]) minRow[i] = a[i][j];

    }

 

    int maxCol[] = new int[m];

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

    {

      maxCol[j] = -1000;

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

        if(a[i][j] > maxCol[j]) maxCol[j] = a[i][j];

    }

   

    int res = 0;

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

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

      if ((a[i][j] == minRow[i]) && (a[i][j] == maxCol[j])) res++;

   

    System.out.println(res);

    con.close();

  }

}