wave algorithm
/thread

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

Главное - талант, способность найти необычное решение проблемы.

Зато сами не могут придумать необычную задачу. Как можно решить такую фигню "необычным способом"?

Но ведь есть уже куча алгоритмов, среди них есть и вполне хорошие(JPS, например).

GeneralElConsul, как по мне, поиск в глубину это не лучший алгоритм поиска пути. Что касается временных ограничений - 4 секунды это очень много и столько может позволить себе занимать только очень большой объем данных - как правило, в таких заданиях время выполнения ожидается намного меньше заявленного максимума.

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

BaHeK, SomeFire, спасибо, был сонный и не заметил.

Это к чему: к тому, что это очень легко или к тому, что это очень сложно? Такой алгоритм на C++ писали на первом курсе - поиск в глубину, менее, чем за 4 секунды(с нормального размера входными). Или им что-то нестандартное нужно с меньшей временной сложностью? Не понятно.
Это просто мысли вслух.