Задача: 752. Open the Lock
Сложность: medium

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

👨‍💻 Алгоритм:

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

var openLock = function(deadends, target) {
    function neighbors(node) {
        const res = [];
        for (let i = 0; i < 4; i++) {
            const x = parseInt(node[i]);
            for (const d of [-1, 1]) {
                const y = (x + d + 10) % 10;
                res.push(node.slice(0, i) + y + node.slice(i + 1));
            }
        }
        return res;
    }

    const dead = new Set(deadends);
    const queue = [['0000', 0]];
    const visited = new Set('0000');

    while (queue.length) {
        const [node, steps] = queue.shift();
        if (node === target) return steps;
        if (dead.has(node)) continue;
        for (const neighbor of neighbors(node)) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, steps + 1]);
            }
        }
    }

    return -1;
};

Ставь 👍 и забирай 📚 Базу знаний