Оптимальный способ проверки соседей элемента в матрице

Question

Мне дана матрица M с размерами n x n.

Я должен написать алгоритм, который возвращает пару x, y, такую, что Mx,y < min(Mx+1,y, Mx,y+1, Mx−1y, Mx,y−1).

Первая идея, которую вы можете придумать, - это, конечно, взять каждый элемент, а затем проверить соседей по одному, чтобы убедиться, что эти отношения верны. Однако алгоритм должен быть оптимальным с точки зрения сложности времени. Здесь я не уверен, как оптимизировать.

Кто-нибудь знает название алгоритма, который я могу искать, или может дать некоторые указания на то, как этот алгоритм может быть оптимизирован?

Я немного подумал и думаю, что, может быть, этот алгоритм можно разбить, чтобы найти минимум в матрице? что наверняка удовлетворяет вышеуказанным отношениям?

Answer 1

Вы ищете локальный минимум. Это очень легко найти, начиная с некоторой записи в матрице и переходя к смежным записям с меньшим значением.

Например, если вы начинаете с (x, y) и M[x+1, y] < M[x, y], затем переходите к (x+1, y). Затем, если M[x+1, y-1] < M[x+1, y], тогда переходите к (x+1, y-1). Повторяйте, пока текущее значение не станет локальным минимумом, что означает, что вы больше не можете переходить к соседнему меньшему значению.