Решение задачи #2 на Python с Яндекс CodeRun — Самый дешёвый путь

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Название задачи: Самый дешёвый путь.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
В каждой клетке прямоугольной таблицы N×MN×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Формат ввода:
Вводятся два числа N и M — размеры таблицы (1≤N≤201≤N≤20, 1≤M≤201≤M≤20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).
Формат вывода

Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Решение:

Python

import heapq

def find_min_path(grid):
    """
    Находит минимальный путь в таблице, используя алгоритм Дейкстры с кучей.

    Args:
        grid: Двумерный список, представляющий таблицу с весами ребер.

    Returns:
        Минимальный вес пути от левого верхнего угла к правому нижнему,
        или -1, если пути нет.
    """

    rows, cols = len(grid), len(grid[0])  # Размеры таблицы
    dist = [[float('inf')] * cols for _ in range(rows)]  # Массив для хранения минимальных расстояний
    dist[0][0] = grid[0][0]  # Инициализируем расстояние до стартовой точки
    heap = [(grid[0][0], 0, 0)]  # Куча для хранения вершин с приоритетом по расстоянию

    while heap:  # Пока куча не пуста
        d, r, c = heapq.heappop(heap)  # Извлекаем вершину с минимальным расстоянием
        if r == rows - 1 and c == cols - 1:  # Если достигли цели
            return d

        for nr, nc in [(r + 1, c), (r, c + 1)]:  # Для каждого соседа
            if 0 <= nr < rows and 0 <= nc < cols:  # Если сосед в границах таблицы
                alt = d + grid[nr][nc]  # Рассчитываем новое расстояние
                if alt < dist[nr][nc]:  # Если новое расстояние меньше текущего
                    dist[nr][nc] = alt  # Обновляем минимальное расстояние
                    heapq.heappush(heap, (alt, nr, nc))  # Добавляем в кучу

    return -1  # Если пути нет

# Ввод данных
n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))

# Вывод результата
result = find_min_path(grid)
print(result)

Объяснение кода

Импорт модуля heapq:
Этот модуль предоставляет инструменты для работы с кучами, которые используются для эффективной реализации алгоритма Дейкстры.

Функция find_min_path
Аргумент grid:
Представляет собой двумерный список, где каждый элемент - это стоимость прохождения через соответствующую клетку.

Переменная dist:
Двумерный список, где dist[i][j] хранит текущую минимальную стоимость пути до клетки (i, j). Изначально все значения инициализируются большим числом float('inf').

Переменная heap:
Куча, которая хранит кортежи вида (расстояние, строка, столбец). Куча позволяет эффективно выбирать следующую вершину для обработки.

Основной цикл while heap:
Извлекает из кучи вершину с минимальным расстоянием.
Проверяет, достигли ли мы целевой клетки (правый нижний угол).
Для всех соседей текущей клетки:
Рассчитывает новое расстояние.
Если новое расстояние меньше текущего минимального расстояния для этой клетки, обновляем dist и добавляем новую вершину в кучу.

Ввод данных:
Считываются размеры таблицы и заполняется список grid значениями из входных данных.

Вызов функции и вывод результата:
Вызывается функция find_min_path и результат (минимальный вес пути) выводится на экран.

Источник решения: hdhAI.com