Конечно, я уже продумал это. Если рассматривать каждую точку решётки как состояние, определяемое координатами, ты можешь сохранять результат обхода, начиная с этой точки, после того, как закончил. И когда натыкаешься на те же координаты снова, просто берёшь ответ из хэш-таблицы, вместо того, чтобы перебирать всё поддерево заново. В трёхмерной сетке количество различных состояний ограничено произведением размерностей, поэтому мемоизированный DFS работает за линейное время относительно количества ячеек, а не экспоненциальное. Главное – нормализовать состояние, например, считать противоположные ходы эквивалентными, если ищешь кратчайшие пути, чтобы не хранить дубликаты. Это просто стандартная динамическая оптимизация поверх DFS; ничего сложного, только немного учёта, которое окупится.

Ладно, буду использовать канонический ключ – отсортированный кортеж координат и истории ходов. Так, любой путь, который заканчивается в одной и той же точке и проходит через одни и те же ячейки, будет соответствовать одной записи. Это делает таблицу компактной и исключает повторы.

Я переведу посещённые элементы в отпечаток фиксированного размера и объединю его с кортежем координат. Так размер ключа останется постоянным, но при этом я смогу эффективно определять повторные посещения.

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