752. Open the Lock

- 2 minutes read - 557 words

Leetcode 752. Open the Lock

題目

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.

The lock initially starts at ‘0000’, a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

想法

這一題在思考的時候可以理解成：

  1. 我們有張圖
  2. 每組數字都是一個節點（例如 0000 或 1234）
  3. 每個節點在圖上皆有相鄰的 24 個節點（每位數字都可以有上下兩種轉法，共有四位數）

那我們就可以試著用 BFS 來做搜尋。

我們的起點都是 0000 ，終點則是 target。

而 dead end 就是擋住路的石頭。

實作

Javascript

var openLock = function (deadends, target) {
    const visited = {};
    const queue = [];
    let depth = 0;

    // 從 0000 出發
    visited["0000"] = true;
    queue.push("0000");

    while (queue.length) {
        // size 會是 queue 中要找的相同深度的節點數
        let size = queue.length;
        while (size > 0) {
            // 要處理的新組合
            let lock = queue.shift();

            // 如果是 DeadEnd 就直接換下一個
            if (deadends.includes(lock)) {
                size--;
                continue;
            }

            // 找到就直接輸出 depth
            if (lock === target) return depth;

            // 找第 i 位數字的上下相鄰節點
            for (let i = 0; i < 4; i++) {
                let n = parseInt(lock[i]);

                // 第 i 位數字往上的相鄰節點
                let go_up = lock.substr(0, i) + (n == 9 ? "0" : n + 1) + lock.substr(i + 1);

                // 第 i 位數字往下的相鄰節點
                let go_down = lock.substr(0, i) + (n == 0 ? "9" : n - 1) + lock.substr(i + 1);

                // 如果沒經過過且也不是死路，就紀錄經過並加入 queue 等待下一輪搜尋
                if (!visited[go_up] && !deadends.includes(go_up)) {
                    visited[go_up] = true;
                    queue.push(go_up);
                }
                if (!visited[go_down] && !deadends.includes(go_down)) {
                    visited[go_down] = true;
                    queue.push(go_down);
                }
            }

            size--;
        }
        // 這個深度的都找完了，深度增加
        depth++;
    }

    // 都沒找到就會來到這，輸出 -1
    return -1;
};