Алгоритм решения двумерной сетки?

Question

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

Проблема: Разработайте алгоритм, который работает за O (n) время (линейное), который может найти один подозрительный дом (точку) на 2D-сетке,Это подозрительно, если он потребляет столько же или больше, чем потребление электроэнергии его двух вертикальных и двух горизонтальных соседей.Примечание: просто хочет, чтобы один подозрительный дом был возвращен

Решение: Даже не уверен, как достичь такого решения.Если вы проверите n домов, вы также можете проверить его четырех соседей.4n / n ^ 2, что упрощает до 4 / n.Это означает, что по мере расширения сетки менее вероятно найти подозрительный дом.

Что я пробовал: - Различные структуры данных (большинство из них nlogn) - Складывание сетки (снова nlogn)

Заранее спасибо.

Редактировать:

Моя ошибка, сетка (nxn) делает число домов n ^ 2, извините за путаницу.

Edit2:

Это именно тот вопрос, может, я неправильно его понимаю?

Полиция ищет дома, в которых потребление электроэнергии особенно велико.Чтобы упростить задачу, представьте, что они исследуют дома, расположенные на сетке n × n.Каждый дом в сети имеет некоторое потребление электроэнергии, e (i, j).Полиция считает дом подозрительным, если его потребление электроэнергии равно или больше, чем у каждого из его вертикальных и горизонтальных соседей.Разработайте алгоритм, который запускается за O (n) раз и возвращает местоположение подозрительного дома.

Answer 1

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

Это займет O (n) времени наnxn grid.

Редактировать: комментаторы правы, в худшем случае это может занять O (n ^ 2) раз.

Answer 2

Локальное оптимальное решение, представленное Китом, на самом деле не будет работать за линейное время.Проблема в том, что он не может гарантировать, что длина пути равна O (n).

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

(Полное решение не предусмотрено, потому что, ну, это назначение) Тем не менее, действительно изящная проблема.Слава его создателю.

[РЕДАКТИРОВАТЬ: Подсказка]

Ранее предлагаемое решение не работает в таких случаях:

X.XXX.XXX.X
X.X.X.X.X.X
X.X.X.X.X.X
X.X.X.X.X.X
XXX.XXX.XXX

где.это действительно небольшое потребление электроэнергии, и x медленно увеличивают потребление электроэнергии.

Что произойдет, если мы запросим средний ряд?

X.XXX.XXX.X
X.X.X.X.X.X
&&&&&&&&&&&
X.X.X.X.X.X
XXX.XXX.XXX

Где находится дом, на который мы смотрели.Нам удалось прорезать путь.Если бы мы начали восхождение на гору в лучшем месте, которое мы нашли, мы смогли бы избежать долгого пути.(Но мы все еще не можем гарантировать, что путь достаточно короткий)

[РЕДАКТИРОВАТЬ: Второй совет]

Сканирование среднего ряда, как упоминалось.Возьмите самое большое значение.Переместитесь вверх или вниз к большему значению (если вы не можете, то эта ячейка сетки является локальной оптимой, и все готово).Теперь рассмотрим путь увеличения ценностей.Невозможно, чтобы путь снова мог пересечь эту среднюю строку, поскольку все значения в этой строке должны быть меньше текущей ячейки.(Поскольку текущая ячейка должна быть больше, чем наибольшее из значений в строке).Это означает, что мы существенно уменьшили проблему в два раза.