Ускорение поиска по сетке на глубину ⇐ Python

[Anonymous]

Сейчас я работаю над кодом 994. Гниющие апельсины. Где описание дано следующим образом:

Вам дана сетка m x n, где каждая ячейка может иметь одно из трех значений; 0 представляет собой пустую ячейку, 1 — свежий фрукт, 2 — гнилой фрукт. Каждую минуту любой свежий апельсин, примыкающий к гнилому апельсину в четырех направлениях, становится гнилым. Возвращает минимальное количество минут, которое должно пройти до тех пор, пока ни в одной ячейке не появится свежий апельсин. Если это невозможно, верните -1.

Моя идея довольно проста. Рассмотрим каждую точку сетки. Если Grid[j] == 1, мы используем поиск в глубину, чтобы определить, сколько времени потребуется, чтобы испортиться. Затем мы просто возвращаем наибольшее такое значение.

Код: Выделить всё

maxTime = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
time = dfs(i,j)
if time == -1:
return -1
else:
maxTime = max(maxTime, time)
return maxTime

Где мой алгоритм dfs реализован следующим образом. Учитывая некоторую координату i,j, мы проверяем вверх, вниз, влево и вправо. Если один из них тоже фрукт, повторяем, пока не встретим гнилой фрукт.

Код: Выделить всё

def dfs(i,j):
directions = [(1,0), (-1,0), (0,1), (0,-1)]
q = collections.deque([(i,j,0)])
while q:
x,y,step = q.popleft()
for i_step, j_step in directions:
i_new = x + i_step
j_new = y + j_step

if (0

Подробнее здесь: [url]https://stackoverflow.com/questions/79355915/speedup-depth-first-search-in-a-grid[/url]