|
|
 |
Условие
На клетчатой бумаге был нарисован лабиринт: квадрат 5×5 (внешняя стена) с выходом шириной в одну клетку, а также внутренние стенки, идущие по линиям сетки. На рисунке мы скрыли от вас все внутренние стенки. Начертите, как они могли располагаться, зная, что числа, стоящие в клетках, показывают наименьшее количество шагов, за которое можно было покинуть лабиринт, стартовав из этой клетки (шаг делается в соседнюю по стороне клетку, если они не разделены стенкой). Достаточно одного примера, пояснения не нужны.
Ответ
См. рисунок.
Комментарий. Можно доказать, что внутренние стенки были расположены именно так. Будем постепенно восстанавливать стенки, исходя из условия задачи. Жирной линией обозначим стенки, в наличии которых мы уверены, линиями из точек обозначим пока не исследованные границы, а в тех местах, где точно есть проход, линию сотрём совсем. Чтобы отдельные клетки были хорошо видны, раскрасим лабиринт в шахматном порядке. Ну и раз уж наш рисунок стал похож на шахматную доску, воспользуемся обозначениями, принятыми у шахматистов, – обозначим столбцы латинскими буквами, а строки – цифрами.
Заметим, что между e4 и e5 точно есть стенка, иначе в e4 было бы 2, а не 10. Теперь посмотрим на клетку d1 с цифрой 6. Из неё до выхода шесть шагов, даже если бы никаких стенок не было, поэтому из d1 к выходу можно пройти по столбцам d и e с одним переходом из d в e. Стенка между e4 и e5 показывает, что переход этот возможен только между d5 и e5, поэтому весь столбец d свободен от поперечных стенок. Наоборот, между d4 и e4, d3 и e3, d2 и e2 стенки есть, иначе из e4 можно было бы выйти быстрее, чем за десять шагов. Вот что у нас получилось:
Из c5 можно выйти за 21 шаг. Поскольку клеток 25, а заходить в "аппендикс" e1–e4 значит удлинять путь, кратчайший путь из c5 пройдёт по всем остальным клеткам лабиринта. И это значит, что последние шесть клеток этого пути начнутся в d1, то есть между столбцами c и d везде, кроме первой строки, есть стенки — иначе в столбец d можно было бы попасть раньше. Путь из a1 по первой строке до d1 и далее уже по известной дороге занимает ровно девять шагов, и теперь понятно, что отклоняться от него нельзя. А тогда между c1 и c2, b1 и b2 есть стенки, иначе длинный путь из c5 можно было бы сократить. Вот что нам теперь понятно:
Путь из c5 проходит через a3, то есть туда из c5 мы должны попасть за четыре шага. С учётом необходимости посещения клетки a5 это можно сделать только одним способом. У нас не должно быть возможности свернуть с этого отрезка пути, поэтому между c5 и c4, b5 и b4, a4 и b4 есть стенки. Стенка есть и между a3 и a2, иначе в a3 было бы 11, а не 17. Вот что сейчас получилось:
Теперь нетрудно восстановить две оставшиеся стенки и получить ответ.
