Snakes and Ladders

Мне попалась задача на LeetCode про змеи и лестницы -_-

Нахлынули вьетнамские флешбэки 😱 и я в детстве всего пару раз играл в эту игру, это воспоминание было разблокировано, но толку от этого конечно 0 и короче не помогло мне это 😅

Кратко просто найти и написать код решения любой игры в змейку и лестницы с полем n x n 🥹

➡️ Задача
На вход подаётся игровое поле размера n x n, представленное в виде двумерного массива. Каждая клетка может быть обычной (-1), содержать лестницу (ведёт на более высокий номер клетки) или змею (ведёт на более низкий номер).

Ты начинаешь на клетке 1 и хочешь добраться до последней клетки n^2, бросая кубик (от 1 до 6). Найди минимальное количество бросков, необходимых для достижения цели, с учётом змей и лестниц.

Поле нумеруется зигзагообразно: первый ряд - слева направо, второй - справа налево и т.д.
Нужно пройти 216 из 216 чтобы задача будет решена

➡️ Сюжетная линия
Я говорил что не больше часа тратить на задачу....
прошло 4 часа короче и 3 из 216 тестов было пройдено😅

Боль приносит, что ходить надо зигзагом. Тут фаза отрицания подъехала. 😔

Я пробил второе дно, когда написал, вроде как классное решение.. как же я ошибался 😅
было пройдено 1 из 216 тестов, yо ничего быстро пофиксил где-то прошло уже 50 из 216. Вообщем я полностью удалил своё решение и начал с начало.

Дальше становилось больнее, господи зигзагом ходить надо (кто вообще придумал 🫣 эту игру) <— тут была фаза торга 😜 до принятия ещё ой как далеко 😭

Дальше я запомнил число 72 из 216. Почему запомнил? потому что тут появились циклы, ЦИКЛЫ из змей и лесенок, Карл! конечно они должны были быть подумал я и начал дальше допиливать код.

Перевал за сотню где то 101 из 216. Оказывается могут быть не оптимальные варианты и переход по змеям не даёт преймущество в ходах 😓

Вообщем решил я её где-то за 5.5 часов 😅 за О(n^2) по памяти, сверхлюди решают за O(k)

➡️ Решение
1⃣ минус одна боль, преобразование двумерную доску в одномерную,
По сути мы начинаем с нижней строки и чередуем направление: одна строка читается слева направо, следующая - справа налево, и так далее и получаем одномернный массив

2⃣ Поиск в ширину
Стартуем с клетки 0 (самая нижняя левая). На каждом шаге пробуем кинуть кубик на 1 - 6 клеток вперёд.
Если попадаем на клетку с лестницей или змеёй, то перемещаемся сразу на указанную клетку. Если нету ничего, тогда мы считаем себя прухлом и ходим будто выбросили 6

3⃣ Используем очередь, чтобы искать самый короткий путь (минимальное количество ходов).

5⃣ Массив visited нужен, чтобы не заходить повторно на уже посещённые клетки и не застрять в цикле.

5⃣ Если не удалось дойти до конца возвращаем -1



Сама задача
909. Snakes and Ladders

Решение C#

public int SnakesAndLadders(int[][] board)
{
    var flatBoard = new int [board.Length * board.Length];
    var index = 0;
    var rightToLeft = true;

    for (var i = board.Length - 1; i >= 0; i--)
    {
        for (var j = 0; j < board.Length; j++)
        {
            if (rightToLeft)
                flatBoard[index] = rightToLeft ? board[i][j] : board[i][board.Length - 1 - j];
            else
                flatBoard[index] = board[i][board.Length - 1 - j];

            index++;
        }

        rightToLeft = !rightToLeft;
    }

    var result = BFS(flatBoard, 0);
    return result;
}

private int BFS(int[] board, int start)
{
    HashSet<int> visited = new();
    Queue<(int position, int step)> queue = new();

    queue.Enqueue((start, 0));
    visited.Add(start);

    while (queue.TryDequeue(out var item))
    {
        if (item.position >= board.Length - 1)
            return item.step;

        for (var dice = 1; dice <= 6; dice++)
        {
            var next = item.position + dice;
            if (next > board.Length - 1)
                break;

            if (visited.Add(next))
            {
                if (board[next] != -1)
                    next = board[next] - 1;

                queue.Enqueue((next, item.step + 1));
            }
        }
    }

    return -1;
}

#leetcode
#medium
#snakesandladders

💡 Channel | ✏ Chat