Решим простую задачу на графы, которая на первый взгляд такой не кажется. Сначала читаем развесистое условие и пытаемся понять, что требуется в задаче: Если переложить на язык алгоритмов, то надо покрыть граф путями. И есть специальные алгоритмы, которые справляются с этой задачей. Но они расчитаны на ориентированные графы. А в этой задаче по каждой дороге можно передвигаться в обоих направлениях. Если упростить задачу и сказать, что есть только один ковбой и спросить, можно ли заблокировать все дороги? Тогда мы получим вариант классической загадки про нарисовать фигуру, не отрывая руки...
Задание максимально простое — нужно обвести конверт, не отрывая руки и не проходя по одной и той же прямой дважды. Задача несложная и отлично подходит для развлечения на переменках. По крайней мере наши родители и прародители (а люди постарше и сами) занимали себя такими головоломками. Подобные задачки также печатались в разных детских и математических журналах. Полагаю, что у всех уже всё получилось, но решение всё таки приведу. 1. Начинаем с левого нижнего угла и идём по диагонали вверх 2. Потом вниз 3...