Как найти максимум среди всех локальных минимумов заданной матрицы?

Question

[Dred Wolf]

Какие есть идеи для решения этой задачи.
Знаю что нужно сначала найти минимумы, а среди них найти максимум.
Минимум (как и максимум) можно найти сравнивая элемент с лежащими от него слева, справа, сверху и снизу элементами.
Существуют 3 варианта расположения элемента матрицы:
1) Угловой (имеет два соседа)
2) Рамка (имеет три соседа, это элементы из краев матрицы)
3) Внутренние (имеют 4 соседа)

Как с помощью языка Си можно решить эту задачу ?

Comments

[AVKor]

Как с помощью языка Си можно решить эту задачу ?

Составив программу на этом языке.

Answer 1

[Александр Ананьев]

Идея такая: составить алгоритм решения на бумажке, затем запрограммировать его.
Проделайте поиск вручную на разных матрицах, как найдете закономерность, можно будет писать алгоритм.

Answer 2

[Wataru]

Алгоритм тривиальный - перебрать все клетки матрицы двумя вложенными циклами. Проверить, что текущая клетка - локальный минимум (сравнить со всеми соседями). Если да, то надо сравнить ее с текущим кандидатом на максимум.

Фактически, тут 2 вложенные задачи: 1) Проверить, является ли значение локальным минимумом 2) Найти максимум в матрице (возможно игнорируя какие-то клетки).

Советую решить задачи раздельно с помощью функций.

Для первой задачи напишите функцию.

bool IsLocalMinumum(int a[][m], int n, int m, int i, int j);

Функция должна перебрать 4 варианта (прибавить/вычесть 1 из первого или второго индекса) и для каждого проверить: 1) сосед есть, т.е. не вышел за границу, 2) значение соседа меньше текущего. Если оба условия выполнились для какого-то направления - вы нашли "плохого" соседа. Текущая клетка не может быть минимумом. Сразу же возвращайте false. В конце функции всегда возвращайте true.

Вторая задача - тривиальна совсем. Можете выбрать максимум из просто одномерного массива? Теперь вместо одного цикла по массиву делайте 2 вложенных по матрице. Потом допишите туда условие, вызывающее вашу IsLocalMinimum. Если вершине не минимум - просто делайте пропускайте клетку. Буквально if (!IsLocalMinimum(a, n, m, i, j)) continue;