Почему это работает
- Все шаги стоят одинаково, поэтому клетки выходят из очереди по возрастанию длины пути: когда последняя клетка вышла впервые, её длина — кратчайшая.
- Клетка получает dist, когда впервые попадает в очередь, и больше в неё не попадает, поэтому ничего не считается дважды.
- Диагональ — это один шаг, поэтому щель между двумя стенами, которые касаются углами, — это проход.
Сложность
Время O(n²): каждая из n² клеток попадает в очередь не больше одного раза и смотрит на 8 соседей. Память O(n²) на dist и очередь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗