Snakes and Ladders

Средняя№909состояния

Квадратная доска n × n пронумерована с 1 в левом нижнем углу: по нижнему ряду, потом обратно по следующему, змейкой. С некоторых клеток начинается лестница или змея, которая переносит на другую клетку. Старт на клетке 1, ход — бросок кубика: идёшь на 1–6 клеток вперёд и, если попал на начало лестницы или змеи, переходишь по ней (за ход только по одной). Найти наименьшее число ходов до клетки n × n или -1, если до неё не дойти. Наш пример: доска 4 × 4, лестница с 2 на 11 и змея с 14 на 4 — ответ 2.

909 Snakes and LaddersРазбор · 1×

Пример: наименьшее число бросков от клетки 1 до 16 на доске 4 × 4 с лестницей 2 → 11 и змеёй 14 → 4.

12345678910111213141516змея 14 → 4лестница 2 → 11очередьначало слева—
не достигнутаждёт в очередитекущая клеткакуда ведёт бросокготова

Старт на клетке 1: 0 ходов

01/38
сначала · назад · пуск · шаг
Скорость
1function snakesAndLadders(board):
2 dist = {1: 0}
3 queue = [1]
4 while queue is not empty:
5 square = queue.popFront()
6 for next in squaresAfterRoll(square):
7 if next == n * n: // the last square
8 return dist[square] + 1
9 if next not in dist:
10 dist[next] = dist[square] + 1
11 queue.pushBack(next)
12 return -1
состояние
dist
{1: 0}
queue
–
square
–
next
–
историянажмите шаг, чтобы вернуться

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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