Робот находится в левом верхнем углу прямоугольника. Размеры прямоугольника неизвестны. Где-то посередине есть вертикальная стена, разделяющая прямоугольник на две части. В этой стене есть проход, при этом проход не является самой верхней или самой нижней клеткой стены. Точное расположение прохода также неизвестно. Напишите для Робота алгоритм, перемещающий робота в правый нижний угол прямоугольника (см. рисунок). Алгоритм должен решать задачу для произвольного размера поля и любого допустимого расположения стен внутри прямоугольного поля. При исполнении алгоритма Робот не должен разрушиться.
Чтобы создать алгоритм, позволяющий роботу перемещаться из левого верхнего угла (0, 0) в правый нижний угол (N, M) прямоугольника с вертикальной стеной и проходом, нужно учесть несколько факторов.
## Шаги алгоритма
1. **Инициализация**:
- Робот начинает в координатах (0, 0).
2. **Поиск прохода**:
- Робот должен перемещаться вниз и находить стену.
- Продолжать двигаться вниз до тех пор, пока не встретит вертикальную стену.
3. **Определение прохода**:
- После того как стена будет обнаружена, робот должен выяснить, где расположен проход.
- Для этого Робот может двигаться вдоль стены вправо (если возможно) или влево, пытаясь найти проход.
4. **Проход через стену**:
- Как только робот находит проход (единственный путь через стену), он должен переместиться в соседнюю область. Например, если проход находится в координатах (i, p), то робот должен переместиться в (i, p).
5. **Движение к правому нижнему углу**:
- Продолжить движение вниз (вправо, если внизу свободно), пока не достигнет правого нижнего угла (N, M).
6. **Обработка препятствий**:
- Если встретит какие-либо препятствия, алгоритм должен уметь менять направление. Например, если робот упирается в стену, он должен разработать стратегию обхода, возвращаясь обратно к предыдущей точке или перемещаясь в другую соседнюю клетку.
## Пример алгоритма на псевдокоде:
```plaintext
1. Начать с (0, 0)
2. пока не достигнута позиция (N, M) {
3. если текущая клетка вниз свободна {
4. двигаться вниз
} иначе {
5. если текущая клетка вправо свободна {
6. двигаться вправо
} иначе {
7. если текущая клетка влево свободна {
8. двигаться влево
} иначе {
9. вернуться назад (если заблокирован)
}
}
}
10. если стена найдена {
11. проверить наличие прохода
12. пройти через проход
}
}
```
## Примечания:
- Алгоритм необходимо адаптировать для обработки всех возможных ситуаций (например, расширяя количество направлений движения в зависимости от местоположения).
- Если прошло заданное количество попыток поиска прохода, робот может установить, что прохода нет и вернуть статус о невозможности выполнения задачи (например, задание провалено).
Этот алгоритм обеспечивает отработку основных принципов навигации в замкнутом пространстве с управляющей логикой, что может быть применимо для различных размеров и форм прямоугольников.
