Для решения данной задачи можно использовать алгоритм Дейкстры или поиск в ширину. Алгоритм Дейкстры - это алгоритм для нахождения кратчайшего пути в графе от одной вершины до всех остальных. Он работает только для графов без отрицательных весов ребер. Алгоритм работает следующим образом: 1. Создаем список вершин, содержащихся в графе. 2. Устанавливаем начальную вершину и ее расстояние равным 0. 3. Устанавливаем все остальные вершины расстоянием "бесконечность". 4. Выбираем вершину с наименьшим расстоянием из списка и помечаем ее как посещенную. 5. Обновляем расстояния до соседних вершин, если новое расстояние меньше текущего. 6. Повторяем шаги 4 и 5, пока все вершины не будут помечены как посещенные или пока не будут обработаны все вершины. В данном случае каждая клетка играет роль вершины графа, а связи между клетками - это ребра графа. Вес каждого ребра будет равен 1, так как участник всегда выбирает кратчайший путь. Теперь рассмотрим применение алгоритма Дейкстры для решения задачи. 1. Создаем двумерный массив, представляющий собой игровое поле размером 8×8. Заполняем его значениями "бесконечность" для каждой клетки. 2. Устанавливаем клетку начального положения (левый верхний угол) и ее значение равным 0. 3. Создаем очередь приоритетов и помещаем в нее клетку начального положения. 4. Пока очередь не пуста: - Извлекаем клетку с наименьшим значением из очереди. - Помечаем клетку как посещенную. - Обновляем значения соседних клеток, если новое значение меньше текущего. - Помещаем соседние клетки в очередь приоритетов. 5. Выводим значения всех клеток на игровом поле. Значение в каждой клетке будет являться длиной кратчайшего пути от начальной клетки до этой клетки. Применение алгоритма Дейкстры позволит найти кратчайший путь от начальной клетки до всех остальных клеток на игровом поле. В конкретном случае задачи мы можем рассмотреть только значение в правом нижнем углу, так как участникам необходимо пройти маршрут из левого верхнего угла в правый нижний угол. Алгоритм Дейкстры имеет сложность O(|V|^2), где |V| - количество вершин графа. В данном случае количество клеток на игровом поле равно 64, поэтому алгоритм будет работать достаточно быстро. Таким образом, алгоритм Дейкстры является эффективным решением задачи нахождения кратчайшего пути для участников соревнований по бегу по пересеченной местности на игровом поле размером 8×8.