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

Красиво и просто решим задачу на 2×2 клетках. Предположим: - клетки называют так: A — верхняя левая, B — верхняя правая, C — нижняя левая, D — нижняя правая. - Робот может двигаться только между соседними клетками по сторонам (вверх/вниз/влево/вправо). - О наличии закрашенной клетки робот узнаёт, когда окажется именно на этой клетке; если он уже в неё попал с начала, решение уже выполнено. Главная идея: пройти по циклу вокруг квадрата, чтобы за минимальное число ходов (ограниченно трем перемещениям) посетить все клетки. Таким образом, независимо от того, в какой клетке начинается робот и в какой клетке закрашена, он гарантированно попадёт в закрашенную клетку не более чем за 3 шага. Стратегия (пошагово): - В начале проверить текущую клетку: если она закрашена — остановиться. - Идём по часовой дуге вокруг квадрата: A → B → D → C → A → ... и повторяем, если нужно. - Продолжаем перемещаться по цепочке, пока не попадём в закрашенную клетку. Доказательство корректности: - В 2×2 квадрате существует цикл посещения всех четырёх клеток за 3 перемещения: при старте в любой клетке можно двигаться так, чтобы через три шага посетить остальные три клетки. - Поскольку закрашенная клетка одна из четырех, и цикл посещает все 4 клетки, в наихудшем случае робот попадёт в закрашенную клетку в ходе этого цикла за не более чем 3 перемещения. - Если же начальная клетка оказалась закрашенной, ответ уже получен без перемещений (0 перемещений). Разбор по шагам для каждого возможного старта (наглядно): 1) Стартап в A - Если закрашена A: 0 moves. - Если закрашена B: A → B (1 move). - Если закрашена D: A → B → D (2 moves). - Если закрашена C: A → B → D → C (3 moves). 2) Стартап в B - Если B закрашена: 0 moves. - Если закрашена D: B → D (1 move). - Если закрашена C: B → D → C (2 moves). - Если закрашена A: B → D → C → A (3 moves). 3) Стартап в C - Если C закрашена: 0 moves. - Если закрашена A: C → A (1 move). - Если закрашена B: C → A → B (2 moves). - Если закрашена D: C → A → B → D (3 moves). 4) Стартап в D - Если D закрашена: 0 moves. - Если закрашена B: D → B (1 move). - Если закрашена A: D → B → A (2 moves). - Если закрашена C: D → B → A → C (3 moves). Итог: - Гарантированное время достижения закрашенной клетки: не более 3 перемещений (макс. 3 шага), если начать не в закрашенной клетке; 0 шагов, если начальная клетка уже закрашена. - Способ: двигаться по циклу A → B → D → C → A ... (посредством фиксированного направления по часовой стрелке). Можно начать с любого старта, проверив на первом же шаге текущую клетку. Если нужно, могу привести аналогичный разбор с другой нотацией клеток или с иллюстрацией схемой. Также можно обсудить альтернативные стратегии (например, обход по другому циклу), но любая такая стратегия для 2×2 будет гарантировать попадание за максимум 3 шага.