Привет, алгоритмические кото-человеки и кошачьи леди! Сегодня у нас задачка, которая как раз для тех, кто хочет вернуться домой с минимальными усилиями после ночи кодинга. Забудьте о котах, кофе и холодильниках. А, стоп, не забудьте! Они же у нас дома.
Суть задачи такова: представьте себе двумерный массив (или матрицу), где каждое значение — это высота конкретного участка местности. Ваша задача — пройти от верхнего левого угла этой матрицы до правого нижнего, минимизируя "усилие", которое равно максимальному абсолютному различию между высотами двух соседних ячеек по вашему маршруту.
Шаг 1: Перед выходом из дома
Перед тем как уйти в магазин за кофе и кормом для кота, нужно знать, как вернуться обратно. Поэтому сначала определим размеры нашего "города" и возможные маршруты.
m, n = len(heights), len(heights[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
🚨 Внимание! Проверьте, что у вас есть карта города, и она не пуста!
Шаг 2: Выходим из дома
Так, клюки в руки и вперед, к приключениям! Начнем с нашего дома.
efforts = {(0, 0): 0}
Шаг 3: По городу
Теперь начнем наш маршрут. Смотрим на ближайшие магазины, кофейни и корм для котов. Выбираем, куда пойдем.
visited = set()
while efforts:
effort, (row, col) = min((effort, rc) for rc, effort in efforts.items())
if (row, col) == (m - 1, n - 1):
return effort # Ура, мы дома!
del efforts[row, col]
visited.add((row, col))
for dx, dy in directions:
x, y = row + dx, col + dy
if 0 <= x < m and 0 <= y < n and (x, y) not in visited:
new_effort = max(effort, abs(heights[x][y] - heights[row][col]))
if new_effort < efforts.get((x, y), float('inf')):
efforts[x, y] = new_effort
🚨 Заметка! Обратите внимание на границы вашего "города". Не заходите в опасные районы!
Финальный код с комментариями
from typing import List
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
# Инициализация переменных: размеры "города" и маршруты
m, n = len(heights), len(heights[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# Устанавливаем начальную "цену" для дома
efforts = {(0, 0): 0}
# Сет для отметки посещенных "магазинов"
visited = set()
# Основной цикл: пока есть непосещенные "магазины"
while efforts:
# Выбираем ближайший "магазин" с минимальной "ценой"
effort, (row, col) = min((effort, rc) for rc, effort in efforts.items())
# Если это дом, возвращаемся
if (row, col) == (m - 1, n - 1):
return effort
# Удаляем текущий "магазин" из списка и добавляем в посещенные
del efforts[row, col]
visited.add((row, col))
# Перебираем все возможные маршруты
for dx, dy in directions:
x, y = row + dx, col + dy
# Проверяем, не выходим ли за границы "города"
if 0 <= x < m and 0 <= y < n and (x, y) not in visited:
# Вычисляем "цену" для нового "магазина"
new_effort = max(effort, abs(heights[x][y] - heights[row][col]))
# Обновляем "цену", если нашли более оптимальный маршрут
if new_effort < efforts.get((x, y), float('inf')):
efforts[x, y] = new_effort
Анекдот на закуску
Почему программисты так редко выходят из дома? Потому что у них там холодильник, кофе и кот.