Shortest Path in Binary Matrix

Средняя№1091сетка

Дана квадратная сетка из 0 и 1: 0 — открыто, 1 — закрыто. Нужно пройти от левой верхней клетки до правой нижней по открытым клеткам, шагая в любую из 8 соседних, в том числе по диагонали. Вернуть длину самого короткого пути в клетках, считая начало и конец, или -1, если пути нет. Наш пример: 0011 / 1010 / 1101 / 1000 — ответ 4.

1091 Shortest Path in Binary MatrixРазбор · 1×

Пример: найти кратчайший путь в клетках по 0011 / 1010 / 1101 / 1000, если ходить можно в 8 сторон.

01230123########очередьначало слева—
открыта, не достигнутав очередитекущая клеткадобавляемый соседготовазакрыта

Обе угловые клетки, (0, 0) и (3, 3), открыты

01/54
сначала · назад · пуск · шаг
Скорость
1function shortestPathBinaryMatrix(grid):
2 if grid[0][0] or the last cell is blocked:
3 return -1
4 dist = table filled with none
5 dist[0][0] = 1 // the path counts cells
6 queue = [(0, 0)]
7 while queue is not empty:
8 (r, c) = queue.popFront()
9 if (r, c) is the last cell:
10 return dist[r][c]
11 for (nr, nc) in 8 open neighbours, no dist:
12 dist[nr][nc] = dist[r][c] + 1
13 queue.pushBack((nr, nc))
14 return -1
состояние
dist
–
queue
–
r
–
c
–
nr
–
nc
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Все шаги стоят одинаково, поэтому клетки выходят из очереди по возрастанию длины пути: когда последняя клетка вышла впервые, её длина — кратчайшая.
  2. Клетка получает dist, когда впервые попадает в очередь, и больше в неё не попадает, поэтому ничего не считается дважды.
  3. Диагональ — это один шаг, поэтому щель между двумя стенами, которые касаются углами, — это проход.

Сложность

Время O(n²): каждая из n² клеток попадает в очередь не больше одного раза и смотрит на 8 соседей. Память O(n²) на dist и очередь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.