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