Решение задачи: Робот в лабиринте (поиск стартовых позиций)

Задача по информатике (Робот в лабиринте: поиск стартовых позиций)

Условие:

Дана программа для Робота:

использовать Робот
алг
нач
  нц пока справа свободно или снизу свободно
    нц пока справа свободно
      вправо
    кц
    нц пока снизу свободно
      вниз
    кц
  кц
кон

Робот находится в одной из клеток поля (см. рисунок).

Рисунок лабиринта:

  A B C D E F
1 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
2 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
3 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
4 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
5 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
6 +---+---+---+---+---+---+

На рисунке также показаны стены внутри лабиринта. Закрашенная клетка - F6.

Вопрос: Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, Робот уцелеет и остановится в закрашенной клетке (клетка F6)?

Повторим разбор программы:

Программа заставляет Робота сначала максимально сдвинуться вправо, затем максимально сдвинуться вниз. И так повторяется, пока он не достигнет клетки, из которой нельзя двигаться ни вправо, ни вниз. Цель - F6.

Стены в лабиринте:

• Горизонтальные:
  • Между B2 и C2
  • Между D2 и E2
  • Между B5 и C5
  • Между D5 и E5
• Вертикальные:
  • Между E2 и E3
  • Между E5 и E6

Давайте перерисуем лабиринт с обозначением стен для наглядности:

  A B C D E F
1 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
2 +---+---+---+---+---+---+
  |   |X  |   |X  |   |   |  (X - стена справа)
3 +---+---+---+---+---+---+
  |   |   |   |   |X  |   |  (X - стена снизу)
4 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
5 +---+---+---+---+---+---+
  |   |X  |   |X  |X  |   |  (X - стена справа, X - стена снизу)
6 +---+---+---+---+---+---+

Закрашенная клетка F6.

Теперь проанализируем каждую клетку, куда Робот придет.

1. Клетки, из которых Робот приходит в F6:

Столбец F: - F6: Робот уже в F6. Условия "справа свободно" и "снизу свободно" ложны. Программа завершается. (1 клетка) - F5: Справа не свободно (граница). Снизу свободно (F6). Робот идет в F6. (1 клетка) - F4: Справа не свободно. Снизу свободно (F5). Робот идет в F5, затем в F6. (1 клетка) - F3: Справа не свободно. Снизу свободно (F4). Робот идет в F4, затем в F5, затем в F6. (1 клетка) - F2: Справа не свободно. Снизу свободно (F3). Робот идет в F3, затем в F4, затем в F5, затем в F6. (1 клетка) - F1: Справа не свободно. Снизу свободно (F2). Робот идет в F2, затем в F3, затем в F4, затем в F5, затем в F6. (1 клетка) Итого: 6 клеток (F1, F2, F3, F4, F5, F6)

Строка 6 (кроме F6): - E6: Справа свободно (F6). Робот идет в F6. (1 клетка) - D6: Справа свободно (E6). Робот идет в E6, затем в F6. (1 клетка) - C6: Справа свободно (D6). Робот идет в D6, затем в E6, затем в F6. (1 клетка) - B6: Справа свободно (C6). Робот идет в C6, затем в D6, затем в E6, затем в F6. (1 клетка) - A6: Справа свободно (B6). Робот идет в B6, затем в C6, затем в D6, затем в E6, затем в F6. (1 клетка) Итого: 5 клеток (A6, B6, C6, D6, E6)

Теперь рассмотрим остальные клетки, двигаясь "назад" от F6 или "вперед" из каждой клетки.

Строка 5: - E5: Справа стена (E5-F5). Снизу стена (E5-E6). Робот застрянет в E5. Не подходит. - D5: Справа стена (D5-E5). Снизу свободно (D6). Робот пойдет в D6, затем в F6. (1 клетка) - C5: Справа свободно (D5). Робот пойдет в D5. Из D5 он пойдет в D6, затем в F6. (1 клетка) - B5: Справа стена (B5-C5). Снизу свободно (B6). Робот пойдет в B6, затем в F6. (1 клетка) - A5: Справа свободно (B5). Робот пойдет в B5. Из B5 он пойдет в B6, затем в F6. (1 клетка) Итого: 4 клетки (A5, B5, C5, D5)

Строка 4: - E4: Справа свободно (F4). Робот пойдет в F4, затем в F6. (1 клетка) - D4: Справа свободно (E4). Робот пойдет в E4, затем в F4, затем в F6. (1 клетка) - C4: Справа свободно (D4). Робот пойдет в D4, затем в E4, затем в F4, затем в F6. (1 клетка) - B4: Справа свободно (C4). Робот пойдет в C4, затем в D4, затем в E4, затем в F4, затем в F6. (1 клетка) - A4: Справа свободно (B4). Робот пойдет в B4, затем в C4, затем в D4, затем в E4, затем в F4, затем в F6. (1 клетка) Итого: 5 клеток (A4, B4, C4, D4, E4)

Строка 3: - E3: Справа свободно (F3). Снизу стена (E3-E4). Робот пойдет в F3, затем в F6. (1 клетка) - D3: Справа свободно (E3). Робот пойдет в E3, затем в F3, затем в F6. (1 клетка) - C3: Справа свободно (D3). Робот пойдет в D3, затем в E3, затем в F3, затем в F6. (1 клетка) - B3: Справа свободно (C3). Робот пойдет в C3, затем в D3, затем в E3, затем в F3, затем в F6. (1 клетка) - A3: Справа свободно (B3). Робот пойдет в B3, затем в C3, затем в D3, затем в E3, затем в F3, затем в F6. (1 клетка) Итого: 5 клеток (A3, B3, C3, D3, E3)

Строка 2: - E2: Справа стена (E2-F2). Снизу свободно (E3). Робот пойдет в E3, затем в F3, затем в F6. (1 клетка) - D2: Справа стена (D2-E2). Снизу свободно (D3). Робот пойдет в D3, затем в E3, затем в F3, затем в F6. (1 клетка) - C2: Справа стена (C2-D2). Снизу свободно (C3). Робот пойдет в C3, затем в D3, затем в E3, затем в F3, затем в F6. (1 клетка) - B2: Справа стена (B2-C2). Снизу свободно (B3). Робот пойдет в B3, затем в C3, затем в D3, затем в E3, затем в F3, затем в F6. (1 клетка) - A2: Справа свободно (B2). Робот пойдет в B2. Из B2 он пойдет в B3, затем в F6. (1 клетка) Итого: 5 клеток (A2, B2, C2, D2, E2)

Строка 1: - E1: Справа свободно (F1). Робот пойдет в F1, затем в F6. (1 клетка) - D1: Справа свободно (E1). Робот пойдет в E1, затем в F1, затем в F6. (1 клетка) - C1: Справа свободно (D1). Робот пойдет в D1, затем в E1, затем в F1, затем в F6. (1 клетка) - B1: Справа свободно (C1). Робот пойдет в C1, затем в D1, затем в E1, затем в F1, затем в F6. (1 клетка) - A1: Справа свободно (B1). Робот пойдет в B1, затем в C1, затем в D1, затем в E1, затем в F1, затем в F6. (1 клетка) Итого: 5 клеток (A1, B1, C1, D1, E1)

Суммируем количество подходящих клеток:

• Столбец F: 6 клеток (F1-F6)
• Строка 6 (без F6): 5 клеток (A6-E6)
• Строка 5 (без F5, E5): 4 клетки (A5, B5, C5, D5)
• Строка 4 (без F4): 5 клеток (A4-E4)
• Строка 3 (без F3): 5 клеток (A3-E3)
• Строка 2 (без F2): 5 клеток (A2-E2)
• Строка 1 (без F1): 5 клеток (A1-E1)

Общее количество = \(6 + 5 + 4 + 5 + 5 + 5 + 5 = 35\) клеток.

Подождите, это слишком много. Давайте перепроверим логику. Программа: 1. Идет вправо до упора. 2. Идет вниз до упора. 3. Повторяет 1 и 2, пока не упрется и вправо, и вниз. Это означает, что Робот всегда будет двигаться к правому нижнему углу, который не заблокирован стенами. Клетка F6 - это правый нижний угол. Если Робот может дойти до F6, то он там и остановится. Единственные клетки, из которых он НЕ дойдет до F6, это те, из которых он застрянет в другом "углу", где нет свободного места ни справа, ни снизу. Давайте найдем такие "углы" в лабиринте. - Клетка E5: Справа стена (E5-F5), снизу стена (E5-E6). Это "угол". Если Робот попадет в E5, он там и застрянет. Теперь нужно определить, из каких стартовых клеток Робот придет в E5. - Из E5: застрянет в E5. - Из D5: Справа стена (D5-E5). Снизу свободно (D6). Робот пойдет в D6. Из D6 он придет в F6. Значит, D5 НЕ застрянет в E5. - Из C5: Справа свободно (D5). Робот пойдет в D5. Из D5 он пойдет в D6, затем в F6. Значит, C5 НЕ застрянет в E5. - Из B5: Справа стена (B5-C5). Снизу свободно (B6). Робот пойдет в B6. Из B6 он придет в F6. Значит, B5 НЕ застрянет в E5. - Из A5: Справа свободно (B5). Робот пойдет в B5. Из B5 он пойдет в B6, затем в F6. Значит, A5 НЕ застрянет в E5. Моя предыдущая оценка для строки 5 была неверной. Давайте перепроверим строку 5: - E5: Справа стена (E5-F5). Снизу стена (E5-E6). Робот застрянет в E5. НЕ подходит. - D5: Справа стена (D5-E5). Снизу свободно (D6). Робот пойдет в D6. Из D6 он придет в F6. ПОДХОДИТ. - C5: Справа свободно (D5). Робот пойдет в D5. Из D5 он пойдет в D6, затем в F6. ПОДХОДИТ. - B5: Справа стена (B5-C5). Снизу свободно (B6). Робот пойдет в B6. Из B6 он придет в F6. ПОДХОДИТ. - A5: Справа свободно (B5). Робот пойдет в B5. Из B5 он пойдет в B6, затем в F6. ПОДХОДИТ. Итого: 4 клетки (A5, B5, C5, D5) из строки 5 подходят. Значит, единственная клетка, из которой Робот не дойдет до F6, это E5. Все остальные 35 клеток (36 - 1) должны приводить в F6. Давайте еще раз внимательно посмотрим на стены. Горизонтальные стены: - B2-C2 - D2-E2 - B5-C5 - D5-E5 Вертикальные стены: - E2-E3 - E5-E6 Рассмотрим клетку E5. Справа от E5 - стена (D5-E5). Нет, это стена между D5 и E5. Стена между E5 и F5 - это граница поля. Стена между E5 и E6 - это вертикальная стена. Давайте уточним, что означает "справа свободно" и "снизу свободно". "Справа свободно" - нет стены справа от текущей клетки ИЛИ это не правая граница поля. "Снизу свободно" - нет стены снизу от текущей клетки ИЛИ это не нижняя граница поля. Перерисуем лабиринт с обозначением стен и границ:

  A B C D E F
1 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
2 +---+---+---+---+---+---+
  |   |---X---|   |---X---|   (X - стена)
3 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
4 +---+---+---+---+---+---+
  |   |   |   |   |   |   |
5 +---+---+---+---+---+---+
  |   |---X---|   |---X---|   (X - стена)
6 +---+---+---+---+---+---+

Анализ клетки E5:

• Справа от E5: F5. F5 - это клетка, не стена. Значит, "справа свободно" - ИСТИНА.
• Снизу от E5: E6. Между E5 и E6 есть вертикальная стена. Значит, "снизу свободно" - ЛОЖЬ.

Итак, из E5: справа свободно (в F5) - ИСТИНА, снизу свободно (в E6) - ЛОЖЬ.