Сложность: medium
В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, верните -1.
Расстояние — это количество пройденных пустых пространств мячиком от начальной позиции (исключительно) до пункта назначения (включительно).
Предположим, что границы лабиринта — это стены. В примере ниже они не указаны.
Пример:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
👨💻 Алгоритм:
1⃣Инициализация
Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.
2⃣Обход лабиринта
Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов.
3⃣Обновление расстояний
Если достигнутая новая позиция может быть достигнута меньшим числом шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода верните минимальное расстояние до пункта назначения или -1, если его нельзя достичь.
😎 Решение:
from collections import deque
class Solution:
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
m, n = len(maze), len(maze[0])
distance = [[float('inf')] * n for _ in range(m)]
distance[start[0]][start[1]] = 0
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
queue = deque([start])
while queue:
s = queue.popleft()
for dx, dy in directions:
x, y, count = s[0] + dx, s[1] + dy, 0
while 0 <= x < m and 0 <= y < n and maze[x][y] == 0:
x += dx
y += dy
count += 1
x -= dx
y -= dy
if distance[s[0]][s[1]] + count < distance[x][y]:
distance[x][y] = distance[s[0]][s[1]] + count
queue.append([x, y])
return -1 if distance[destination[0]][destination[1]] == float('inf') else distance[destination[0]][destination[1]]
Ставь 👍 и забирай 📚 Базу знаний