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

Узнай цену своей работы

Формулировка задачи:

Задана матрица K, содержащая n строк и m столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце. Найдите количество седловых точек заданной матрицы. Входные данные: Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 750). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно kij. Все kij по модулю не превосходят 1000. Выходные данные: Выведите ответ на задачу. Пример: Входные данные 2 2 0 0 0 0 Выходные данные 4 Вот мое решение, проходит 33 теста из 35. Целый день ищу ошибку и никак не могу найти.
var
  n, m, i, j, s: longint;
  a: array[1..750, 1..750] of integer;
  b, c: array[1..750] of integer;
begin
  read(n, m);
  for i := 1 to n do
    for j := 1 to m do
      read(a[i, j]);
  for i := 1 to n do
  begin
    b[i] := 1;
    for j := 2 to m do
      if a[i, b[i]] < a[i, j] then b[i] := j;
  end;
  for j := 1 to m do
  begin
    c[j] := 1;
    for i := 2 to n do
      if a[c[j], j] > a[i, j] then c[j] := i;
  end;
  for i := 1 to n do
    for j := 1 to m do
      if (a[i, j] = a[i, b[i]]) and (a[i, j] = a[c[j], j]) then inc(s);
  write(s);
end.
b[i] - индекс максимального элемента в i-той строке c[j] - индекс минимального элемента в j-том столбце

Решение задачи: «Найдите количество седловых точек заданной матрицы»

textual
Листинг программы
const nn=750; mm=750;
var
  r: array [1..nn] of Integer;
  c: array [1..mm] of Integer;
  n, m, i, j, k: Integer;
  s: Longint;
begin
  Read(n,m); s:=0;
  for j:=1 to m do Read(c[j]); { i=1 }
  for i:=2 to n do
    for j:=1 to m do begin
      Read(k);
      if           c[j]<k  then c[j]:=k; { max j-го столбца }
      if (j=1) or (r[i]>k) then r[i]:=k; { min i-й строки }
     end;
  for i:=1 to n do for j:=1 to m do Inc(s,Ord(r[i]=c[j]));
  WriteLn(s);
end.

Объяснение кода листинга программы

В данном коде происходит чтение матрицы из файла. Сначала объявляются две переменные nn и mm, которые представляют собой размеры матрицы. Далее объявляется массив r, который будет хранить значения столбцов матрицы. Также объявляется массив c, который будет хранить значения строк матрицы. После этого объявляются переменные n, m, i, j и k, которые будут использоваться для чтения и обработки значений матрицы. Затем происходит чтение значений из файла. Для этого используется цикл for, который проходит по каждой ячейке матрицы. Внутри цикла происходит чтение значений из файла и сохранение их в соответствующих ячейках массива c. После чтения всех значений матрицы происходит вычисление количества седловых точек. Для этого используется еще один цикл for, который проходит по каждой строке матрицы. Внутри цикла происходит сравнение текущей строки с предыдущей и сохранение минимального значения в переменной s. В конце выводится значение переменной s, которое и является количеством седловых точек в матрице.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.727 из 5
Похожие ответы