У робота нет цели, только путь Юный ученик АИши Саша собрал робота-доставщика и назвал его Доставчик. Перед инженером стоит ответственная задача: научить Доставчика находить…
У робота нет цели, только путь Юный ученик АИши Саша собрал робота-доставщика и назвал его Доставчик. Перед инженером стоит ответственная задача: научить Доставчика находить оптимальный маршрут в городе. Для этого Саша приготовил специальное игровое поле5×10 . Оно разделено на квадратные ячейки, каждая из которых может быть либо свободной, либо занятой препятствием. Робот начинает движение из левого верхнего угла поля(1,1) и должен добраться до правого нижнего угла (5,10). Начальная и конечная ячейки свободны. Доставчик только учится перемещаться, поэтому за один ход он может выполнить одно из следующих действий: 1.Передвинуться на соседнюю ячейку вниз. Если робот находится в ячейке , то он может попасть в ячейку . Передвинуться на соседнюю ячейку вправо. Если робот находится в ячейке , то он может попасть в ячейку . Перепрыгнуть через соседнюю ячейку вниз. Если робот находится в ячейке , то он может попасть в ячейку , минуя . Перепрыгнуть через соседнюю ячейку вправо. Если робот находится в ячейке , то он может попасть в ячейку , минуя . Перемещение первого и второго типа стоит РобоДжоуль. Перемещение третьего и четвёртого типа стоит РобоДжоуля. Доставчик сломается, если попадёт на занятую препятствием ячейку или выйдет за пределы поля. Помогите Саше определить, какова минимальная стоимость передвижения от начальной до конечной точки. Ввод: Квадратное поле размера . Символ «.» обозначает свободную ячейку, а символ «#» — препятствие. Вывод: Минимальная стоимость передвижения. Номера команд, которые должен выполнить робот, чтобы добраться до конечной точки за минимальную стоимость. Если подходящих путей несколько, выведите любой из них. Пример для поля : Минимальная стоимость передвижения: Символами отмечен возможный путь робота. Символом — начало пути. Маршрут: . Минимальная стоимость передвижения Введите целое число или десятичную дробь… Маршрут
Чтобы помочь Саше определить минимальную стоимость передвижения от начальной точки (1,1) до конечной точки (5,10) на игровом поле 5×10, мы можем использовать алгоритм поиска пути, например, алгоритм Дейкстры или A* (A-звезда). Однако, для простоты, мы рассмотрим подход с использованием BFS (поиск в ширину) для нахождения кратчайшего пути.
Шаг 1: Понимание доступных перемещений
Робот может перемещаться следующим образом:
- На одну ячейку вниз (стоимость 1 РобоДжоуль)
- На одну ячейку вправо (стоимость 1 РобоДжоуль)
- Перепрыгнуть через одну ячейку вниз (стоимость 2 РобоДжоуля)
- Перепрыгнуть через одну ячейку вправо (стоимость 2 РобоДжоуля)
Шаг 2: Алгоритм для поиска маршрута
- Создаем матрицу для представления игрового поля, где
.— свободная ячейка, а#— препятствие. - Инициализируем очередь, которая будет хранить состояние робота: текущие координаты, общая стоимость передвижения и путь (последовательность команд).
- Начинаем с начальной точки (1, 1) и добавляем ее в очередь.
- В каждом шаге из очереди извлекаем текущее состояние робота, проверяем все возможные перемещения, и если новое состояние свободно, добавляем его в очередь с обновленной стоимостью и путем.
- Как только достигаем конечной точки (5, 10), выводим минимальную стоимость и путь.
Шаг 3: Пример реализации
Вот примерный алгоритм на псевдокоде:
field = [
['.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],
['.', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['#', '#', '#', '.', '#', '#', '#', '#', '#', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.']
]
n = 5 # количество строк
m = 10 # количество столбцов
start = (0, 0) # (1, 1) в человеческих координатах
end = (4, 9) # (5, 10)
# BFS алгоритм
queue = [(start, 0, [])] # (положение, стоимость, путь)
visited = set()
min_cost = float('inf')
best_path = []
while queue:
(x, y), cost, path = queue.pop(0)
if (x, y) == end:
if cost < min_cost:
min_cost = cost
best_path = path
# Проверить все доступные движения
moves = [
((x + 1, y), 1, 1), # вниз
((x, y + 1), 1, 2), # вправо
((x + 2, y), 2, 3), # перепрыгнуть вниз
((x, y + 2), 2, 4), # перепрыгнуть вправо
]
for (new_x, new_y), move_cost, command in moves:
if 0 <= new_x < n and 0 <= new_y < m and field[new_x][new_y] == '.':
if (new_x, new_y) not in visited:
visited.add((new_x, new_y))
queue.append(((new_x, new_y), cost + move_cost, path + [command]))
# Результаты
print(f"Минимальная стоимость передвижения: {min_cost}")
print("Маршрут: ", ' '.join(map(str, best_path)))
Этот алгоритм показывает, как найти минимальную стоимость передвижения и получить маршрут робота. Вам следует запустить этот алгоритм на вашем игровом поле, чтобы получить конкретные значения. Убедитесь, что вы корректно воспринимаете координаты: они начинаются с 0 в программировании, а не с 1, как в текстовом описании задачи.
