Задача № 2 Робот находится в одной из клеток квадрата 2×2. В квадрате есть одна горизонтальная стенка шириной в одну клетку, где именно — неизвестно. Роботу надо оказаться в правой верхней клетке квадрата.

Задача: Робот в одной из клеток квадрата 2×2. Есть одна горизонтальная стенка шириной в одну клетку, место которой неизвестно. Нужно оказаться в правой верхней клетке (B). Допущения (чтобы задача была ясна): - Робот может двигаться в соседнюю клетку по горизонтали или вертикали. - Если движение невозможно из-за границы поля или стены, робот остаётся в той же клетке. - Стенка остается фиксированной на всём время решения и не меняет положение во время движения робота. - Нужна гарантированная стратегия, которая привести робота в клетку B независимо от того, в какой клетке он начинает и где находится стена (варианты стены: между A–C или между B–D). Обозначения клеток: - A = верхняя левая (1,1) - B = верхняя правая (1,2) — цель - C = нижняя левая (2,1) - D = нижняя правая (2,2) Стратегия (универсальная, работает независимо от местоположения стены): - Повторяй цикл из четырёх ходов: Right, Up, Left, Up. - Останавливайся сразу, как только окажешься в клетке B. - Если ты начинаешь в B, можно сразу остановиться (цель уже достигнута). Объяснение корректности по случаям: - Случай 1: стена находится между A и C (W_L). - A: Right → B (достигнута цель сразу). - B: уже в B. - C: Right → D, Up → B (путь через D в верхнюю клетку). - D: Up → B. Таким образом, при W_L цель достигается в течение первых двух ходов в любом начальном положении. - Случай 2: стена находится между B и D (W_R). - A: Right → B (достигнута цель сразу). - B: уже в B. - C: Right → D (разворачиваемся к правой колонке), Up не срабатывает (стенка между B и D), поэтому остаётся в D; следующий ход Left → C, затем Up → A, затем Right → B. То есть цель достигается на 5-м ходе цикла. - D: Right не движет, Up не работает (стенка между B и D), Left → C, Up → A, Right → B. Также достигается в ходе цикла (на шаге, когда достигнешь B после перехода через верхнюю строку). Итог: - Универсальная последовательность Right → Up → Left → Up, повторяемая при необходимости, гарантированно доведет робота до клетки B в любом из четырёх стартовых положений и при любой из двух возможных позиций горизонтальной стенки. - В худшем случае достижение B происходит за 5 ходов (пример: старт в C или D при W_R). Пошаговый план для практического выполнения: - Шаг 1: попытаться пойти вправо. - Шаг 2: попытаться пойти вверх. - Шаг 3: попытаться пойти влево. - Шаг 4: попытаться пойти вверх. - При необходимости повторяй шаги 1–4 снова и снова. - Как только окажешься в клетке B, остановись (цель достигнута). Пример иллюстративного прохождения: - Начальная позиция C, стена W_R: 1) Right: C → D 2) Up: движение вверх не возможно (стенка), остаётся D 3) Left: D → C 4) Up: C → A 5) Right: A → B (цель достигнута) Зачем эта стратегия работает: - В 2×2 варианте существует только два возможных местоположения горизонтальной стенки, что создаёт две разные схемы обхода. Приведённый цикл ходов учитывает обе ситуации и гарантированно выводит к цели независимо от того, где стена и где начальная клетка. Поскольку цель — быть в B, алгоритм специально строится так, чтобы добавить пути, обеспечивающие попадание в B в любом случае. Если хочешь, могу привести краткую версию решения без циклического повторения (для случая, когда известно начальное положение или положение стены), но данная универсальная схема подходит под любые варианты и гарантирует успех.