Задача: 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.

😎 Решение:

func openLock(_ deadends: [String], _ target: String) -> Int {
    func neighbors(_ node: String) -> [String] {
        var res = [String]()
        let nodeArray = Array(node)
        for i in 0..<4 {
            var nodeChars = nodeArray
            let x = Int(String(nodeChars[i]))!
            for d in [-1, 1] {
                let y = (x + d + 10) % 10
                nodeChars[i] = Character(String(y))
                res.append(String(nodeChars))
            }
        }
        return res
    }
    
    let dead = Set(deadends)
    var queue = [(String, Int)]()
    queue.append(("0000", 0))
    var visited = Set<String>()
    visited.insert("0000")
    
    while !queue.isEmpty {
        let (node, steps) = queue.removeFirst()
        if node == target {
            return steps
        }
        if dead.contains(node) {
            continue
        }
        for neighbor in neighbors(node) {
            if !visited.contains(neighbor) {
                visited.insert(neighbor)
                queue.append((neighbor, steps + 1))
            }
        }
    }
    
    return -1
}

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