Задача по информатике (Робот в лабиринте: поиск стартовых позиций)
Условие:
Дана программа для Робота:
использовать Робот
алг
нач
нц пока справа свободно или снизу свободно
нц пока справа свободно
вправо
кц
нц пока снизу свободно
вниз
кц
кц
кон
Робот находится в одной из клеток поля (см. рисунок).
Рисунок лабиринта:
A B C D E F 1 +---+---+---+---+---+---+ | | | | | | | 2 +---+---+---+---+---+---+ | | | | | | | 3 +---+---+---+---+---+---+ | | | | | | | 4 +---+---+---+---+---+---+ | | | | | | | 5 +---+---+---+---+---+---+ | | | | | | | 6 +---+---+---+---+---+---+
На рисунке также показаны стены внутри лабиринта. Закрашенная клетка - F6.
Вопрос: Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, Робот уцелеет и остановится в закрашенной клетке (клетка F6)?
Разбор программы Робота:
Программа состоит из вложенных циклов. Давайте разберем её по шагам:
нц пока справа свободно или снизу свободно // Внешний цикл: выполняется, пока есть куда двигаться вправо или вниз
нц пока справа свободно // Внутренний цикл 1: двигаемся вправо, пока это возможно
вправо
кц
нц пока снизу свободно // Внутренний цикл 2: двигаемся вниз, пока это возможно
вниз
кц
кц
Что делает программа:
- Внешний цикл:
нц пока справа свободно или снизу свободно. Этот цикл будет повторяться до тех пор, пока Робот не окажется в правом нижнем углу, где нет свободного места ни справа, ни снизу. - Внутренний цикл 1:
нц пока справа свободно вправо кц. Робот будет двигаться вправо до упора (до стены или до правой границы поля). - Внутренний цикл 2:
нц пока снизу свободно вниз кц. После того как Робот упрётся вправо, он начнёт двигаться вниз до упора (до стены или до нижней границы поля).
Таким образом, программа заставляет Робота сначала максимально сдвинуться вправо, затем максимально сдвинуться вниз. И так повторяется, пока он не достигнет клетки, из которой нельзя двигаться ни вправо, ни вниз. Это означает, что Робот всегда будет стремиться к правому нижнему углу поля, который не заблокирован стенами.
Целевая клетка: F6 (правый нижний угол).
Условие "уцелеет": Робот не должен врезаться в стену. Программа использует условия "справа свободно" и "снизу свободно", что гарантирует, что Робот не врежется в стену, если он находится в пределах поля. Единственный способ "не уцелеть" - это если он попытается выйти за пределы поля, но в КуМире это обычно приводит к остановке, а не "гибели" в смысле задачи. Здесь "уцелеет" означает, что он успешно завершит программу, не столкнувшись с неразрешимой ситуацией (например, попыткой движения в занятую клетку, что в данной программе исключено).
Анализ лабиринта и движения Робота:
Давайте проследим путь Робота из разных стартовых клеток. Робот всегда будет двигаться сначала вправо до упора, затем вниз до упора, затем снова вправо до упора, и так далее, пока не достигнет клетки F6.
Нам нужно найти все стартовые клетки, из которых Робот, следуя этой программе, придет в F6.
Рассмотрим лабиринт по столбцам и строкам. Стены: - Между B2 и C2 - Между D2 и E2 - Между E2 и F2 (это не стена, а граница поля) - Между B5 и B6 - Между D5 и E5 - Между E5 и E6
Давайте проанализируем, куда придет Робот из каждой клетки.
Клетка F6: Это целевая клетка. Если Робот начинает в F6, то "справа свободно" - ложь, "снизу свободно" - ложь. Внешний цикл не выполнится. Робот останется в F6. Значит, F6 - одна из искомых клеток.
Клетки в столбце F (F1-F5): - Из F5: "справа свободно" - ложь. "снизу свободно" - истина (F6 свободно). Робот пойдет вниз в F6. Остановится в F6. - Из F4: "справа свободно" - ложь. "снизу свободно" - истина (F5 свободно). Робот пойдет вниз в F5, затем из F5 в F6. Остановится в F6. - Из F3: "справа свободно" - ложь. "снизу свободно" - истина (F4 свободно). Робот пойдет вниз в F4, затем в F5, затем в F6. Остановится в F6. - Из F2: "справа свободно" - ложь. "снизу свободно" - истина (F3 свободно). Робот пойдет вниз в F3, затем в F4, затем в F5, затем в F6. Остановится в F6. - Из F1: "справа свободно" - ложь. "снизу свободно" - истина (F2 свободно). Робот пойдет вниз в F2, затем в F3, затем в F4, затем в F5, затем в F6. Остановится в F6. Все клетки столбца F (F1-F6) приводят в F6. Это 6 клеток.
Клетки в строке 6 (A6-E6): - Из E6: "справа свободно" - истина (F6 свободно). Робот пойдет вправо в F6. Остановится в F6. - Из D6: "справа свободно" - истина (E6 свободно). Робот пойдет вправо в E6, затем в F6. Остановится в F6. - Из C6: "справа свободно" - истина (D6 свободно). Робот пойдет вправо в D6, затем в E6, затем в F6. Остановится в F6. - Из B6: "справа свободно" - истина (C6 свободно). Робот пойдет вправо в C6, затем в D6, затем в E6, затем в F6. Остановится в F6. - Из A6: "справа свободно" - истина (B6 свободно). Робот пойдет вправо в B6, затем в C6, затем в D6, затем в E6, затем в F6. Остановится в F6. Все клетки строки 6 (A6-F6) приводят в F6. Это 6 клеток. (F6 уже учтена)
Теперь рассмотрим остальные клетки, учитывая стены.
Строка 5: - Из E5: "справа свободно" - ложь (стена между E5 и F5). "снизу свободно" - ложь (стена между E5 и E6). Робот застрянет в E5. Не подходит. - Из D5: "справа свободно" - истина (E5 свободно). Робот пойдет в E5. Из E5 он застрянет. Не подходит. - Из C5: "справа свободно" - истина (D5 свободно). Робот пойдет в D5, затем в E5, где застрянет. Не подходит. - Из B5: "справа свободно" - истина (C5 свободно). Робот пойдет в C5, затем в D5, затем в E5, где застрянет. Не подходит. - Из A5: "справа свободно" - истина (B5 свободно). Робот пойдет в B5, затем в C5, затем в D5, затем в E5, где застрянет. Не подходит. Ни одна клетка из A5-E5 не приводит в F6.
Строка 4: - Из F4: уже учтено (приводит в F6). - Из E4: "справа свободно" - истина (F4 свободно). Робот пойдет в F4. Из F4 он придет в F6. Подходит. - Из D4: "справа свободно" - истина (E4 свободно). Робот пойдет в E4, затем в F4, затем в F6. Подходит. - Из C4: "справа свободно" - истина (D4 свободно). Робот пойдет в D4, затем в E4, затем в F4, затем в F6. Подходит. - Из B4: "справа свободно" - истина (C4 свободно). Робот пойдет в C4, затем в D4, затем в E4, затем в F4, затем в F6. Подходит. - Из A4: "справа свободно" - истина (B4 свободно). Робот пойдет в B4, затем в C4, затем в D4, затем в E4, затем в F4, затем в F6. Подходит. Все клетки A4-F4 приводят в F6. Это 6 клеток. (F4 уже учтена)
Строка 3: - Из F3: уже учтено (приводит в F6). - Из E3: "справа свободно" - истина (F3 свободно). Робот пойдет в F3. Из F3 он придет в F6. Подходит. - Из D3: "справа свободно" - истина (E3 свободно). Робот пойдет в E3, затем в F3, затем в F6. Подходит. - Из C3: "справа свободно" - истина (D3 свободно). Робот пойдет в D3, затем в E3, затем в F3, затем в F6. Подходит. - Из B3: "справа свободно" - истина (C3 свободно). Робот пойдет в C3, затем в D3, затем в E3, затем в F3, затем в F6. Подходит. - Из A3: "справа свободно" - истина (B3 свободно). Робот пойдет в B3, затем в C3, затем в D3, затем в E3, затем в F3, затем в F6. Подходит. Все клетки A3-F3 приводят в F6. Это 6 клеток. (F3 уже учтена)
Строка 2: - Из F2: уже учтено (приводит в F6). - Из E2: "справа свободно" - ложь (стена между E2 и F2). "снизу свободно" - истина (E3 свободно). - Робот из E2 не может пойти вправо. - Он пойдет вниз в E3. Из E3 он придет в F6. Значит, E2 подходит. - Из D2: "справа свободно" - ложь (стена между D2 и E2). "снизу свободно" - истина (D3 свободно). - Робот из D2 не может пойти вправо. - Он пойдет вниз в D3. Из D3 он придет в F6. Значит, D2 подходит. - Из C2: "справа свободно" - истина (D2 свободно). Робот пойдет в D2. Из D2 он придет в F6. Значит, C2 подходит. - Из B2: "справа свободно" - ложь (стена между B2 и C2). "снизу свободно" - истина (B3 свободно). - Робот из B2 не может пойти вправо. - Он пойдет вниз в B3. Из B3 он придет в F6. Значит, B2 подходит. - Из A2: "справа свободно" - истина (B2 свободно). Робот пойдет в B2. Из B2 он придет в F6. Значит, A2 подходит. Все клетки A2-F2 приводят в F6. Это 6 клеток. (F2 уже учтена)
Строка 1: - Из F1: уже учтено (приводит в F6). - Из E1: "справа свободно" - истина (F1 свободно). Робот пойдет в F1. Из F1 он придет в F6. Подходит. - Из D1: "справа свободно" - истина (E1 свободно). Робот пойдет в E1, затем в F1, затем в F6. Подходит. - Из C1: "справа свободно" - истина (D1 свободно). Робот пойдет в D1, затем в E1, затем в F1, затем в F6. Подходит. - Из B1: "справа свободно" - истина (C1 свободно). Робот пойдет в C1, затем в D1, затем в E1, затем в F1, затем в F6. Подходит. - Из A1: "справа свободно" - истина (B1 свободно). Робот пойдет в B1, затем в C1, затем в D1, затем в E1, затем в F1, затем в F6. Подходит. Все клетки A1-F1 приводят в F6. Это 6 клеток. (F1 уже учтена)
Подсчет:
Клетки, из которых Робот приходит в F6:
- Весь столбец F: F1, F2, F3, F4, F5, F6 (6 клеток)
- Вся строка 6: A6, B6, C6, D6, E6 (F6 уже учтена) (5 клеток)
- Строка 5: Ни одной (из-за стен E5-F5 и E5-E6)
- Строка 4: A4, B4, C4, D4, E4 (F4 уже учтена) (5 клеток)
- Строка 3: A3, B3, C3, D3, E3 (F3 уже учтена) (5 клеток)
- Строка 2: A2, B2, C2, D2, E2 (F2 уже учтена) (5 клеток)
- Строка 1: A1, B1, C1, D1, E1 (F1 уже учтена) (5 клеток)
Давайте пересчитаем более систематически, отмечая клетки на поле.
Поле 6x6 = 36 клеток.
Клетки, которые приводят в F6:
Столбец F: F1, F2, F3, F4, F5, F6 (6 клеток)
Строка 6: A6, B6, C6, D6, E6 (F6 уже учтена) (5 клеток)
Рассмотрим остальные клетки:
A1: -> B1 -> C1 -> D1 -> E1 -> F1 -> F2 -> F3 -> F4 -> F5 -> F6. (Подходит)
B1: -> C1 -> D1 -> E1 -> F1 -> F2 -> F3 -> F4 -> F5 -> F6. (Подходит)
C1: -> D1 -> E1 -> F1 -> F2 -> F3 -> F4 -> F5 -> F6. (Подходит)
D1: -> E1 -> F1 -> F2 -> F3 -> F4 -> F5 -> F6. (Подходит)
E1: -> F1 -> F2 -> F3 -> F4 -> F5 -> F6. (Подходит)
A2: -> B2 (стена справа) -> B3 -> C3 -> D3 -> E3 -> F3 -> F4 -> F5 -> F6. (Подходит)
B2: (стена справа) -> B3 -> C3 -> D3 -> E3 -> F3 -> F4 -> F5 -> F6. (Подходит)
C2: -> D2 (стена справа) -> D3 -> E3 -> F3 -> F4 -> F5 -> F6. (Подходит)
D2: (стена справа) -> D3 -> E3 -> F3 -> F4 -> F5 -> F6. (Подходит)
<