Давайте посмотрим на нашу сегодняшнюю проблему кодирования, которую мы должны решить.
Постановка проблемы: -
Змеи и лестницы — это игра на доске 10 х 10, цель которой — добраться от клетки 1 до клетки 100. На каждом ходу игроки бросают шестигранный кубик и перемещаются вперед на количество клеток, равное результату. Если они приземлятся на квадрат, представляющий змею или лестницу, они будут перенесены вперед или назад, соответственно, на новый квадрат.
Найдите наименьшее количество ходов, необходимое для игры в змейки и лестницы.
Для удобства вот квадраты, изображающие змей и лестницы, и их исходы:
змеи = {16:6, 48:26, 49:11, 56:53, 62:19, 64:60, 87:24, 93:73, 95:75, 98:78}
лестницы = {1:38, 4:14, 9:31, 21:42, 28:84, 36:44, 51:67, 71:91, 80:100}
Давайте начнем со всей информации, которую мы знаем об игре.
- Начинаем с позиции 0.
- Мы используем 6-гранный кубик, чтобы играть ходы.
- Игра заканчивается на 100-й позиции.
- Если мы находимся на клетке, которая соединяется с лестницей, мы быстро продвигаемся вверх.
- Если мы находимся на ячейке со змеиным ртом, мы спускаемся к ее хвосту.
Теперь, когда я ясно вижу проблему, первое, что приходит мне в голову, это использовать BFS (поиск в ширину).
Мы начинаем с 0-й позиции с 0 шагами, добавляем наш кортеж (0,0) в нашу очередь и для каждых 1-6 мест, которые мы можем покрыть с помощью 6-гранного кубика, мы вычисляем следующее место, на которое мы можем перейти.
Мы также должны рассмотреть ячейки со змеями, потому что что, если может быть любое оптимальное решение, которое возникает быстро, просто потому, что мы находимся в хвосте змеи, а следующая ячейка - это большая лестница прямо на 100-е место.
Я надеюсь, что эта проблема была прямой и легкой для понимания. Я также прилагаю свой пример кода для этого на С++. Временная сложность этой задачи будет O(n).
