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