Когда обход сетки может идти только вправо и вверх

Условие

На сетке разрешены произвольные препятствия и движения в четыре стороны. Можно ли всегда отбросить переходы влево и вниз, если старт находится в левом нижнем углу?

Ответ

Нет: обход препятствия может требовать временного уменьшения координаты. Оставлять два направления можно только при доказанном свойстве конкретного множества разрешённых клеток.

Контрпример в полосе из трёх строк: старт (0,0), цель (3,0), а (2,0) запрещена. Путь через (1,1), (2,1), (3,1) требует затем шага вниз. Монотонный обход его не найдёт. Для специальных ограничений по координатам сначала докажите сохранение достижимости, а не переносите оптимизацию по аналогии.