[LeetCode][Medium] 752. Open the Lock

Leetcode 網址: https://leetcode.com/problems/open-the-lock/

題目說明:

題目大意是有一個四位數的密碼鎖，每一位數字可以透過旋轉 (也就是可以9->0, 0->9) 來設定，

但是這個密碼鎖有被設定炸彈，轉到指定的密碼清單時 (deadends)，會爆炸。

給定一組密碼 (target) 以及指定的密碼清單 (deadends)，

請問從 0000 轉到 target 不爆炸的最短轉動次數是多少 ?

解題說明:

這題可以直接把四位數的密碼鎖想成四維 (w, x, y, z) 的地圖，起始位置為 0 0 0 0，

每一步可以移動一個維度 (w + 1, w - 1, x + 1, x - 1, y + 1, y - 1, z + 1, z - 1)，

而指定的密碼清單則為地圖的路障 (牆壁 or 死路)，

因此這個問題直接套用解圖論的算法 Breadth-first Search 或是 Depth-first Search 即可。

程式碼

class Solution {
public:
    int table[10][10][10][10];
    struct Lock { char w, x, y, z; };
    
    inline int rotate(int v, int way) {
        v = v + way;
        return v >= 10 ? 0 : (v < 0 ? 9 : v);
    }
    
    inline void addQueue(queue& q, char w, char x, char y, char z, int step) {
        if (table[w][x][y][z] != -1 || table[w][x][y][z] == INT_MAX) return;
        table[w][x][y][z] = step;
        q.push({w, x, y, z});
    }
    
    int openLock(vector& deadends, string target) {
        memset(table, 0xFFFFFFFF, sizeof(table));
        for (int i = 0; i < deadends.size(); i++) {
            const char* str = deadends[i].c_str();
            table[str[0] - '0'][str[1] - '0'][str[2] - '0'][str[3] - '0'] = INT_MAX;
        }
        int w = target.c_str()[0] - '0', x = target.c_str()[1] - '0', y = target.c_str()[2] - '0', z = target.c_str()[3] - '0';
        
        // Breadth-First Search
        queue q;
        if (table[0][0][0][0] != INT_MAX) {
            q.push({0, 0, 0, 0});
            table[0][0][0][0] = 0;
        }

        while (q.size() > 0 && table[w][x][y][z] == -1) {
            Lock l = q.front();
            int step = table[l.w][l.x][l.y][l.z] + 1;
            addQueue(q, rotate(l.w, 1), l.x, l.y, l.z, step);
            addQueue(q, rotate(l.w, -1), l.x, l.y, l.z, step);
            addQueue(q, l.w, rotate(l.x, 1), l.y, l.z, step);
            addQueue(q, l.w, rotate(l.x, -1), l.y, l.z, step);
            addQueue(q, l.w, l.x, rotate(l.y, 1), l.z, step);
            addQueue(q, l.w, l.x, rotate(l.y, -1), l.z, step);
            addQueue(q, l.w, l.x, l.y, rotate(l.z, 1), step);
            addQueue(q, l.w, l.x, l.y, rotate(l.z, -1), step);
            q.pop();
        }
        
        return table[w][x][y][z] == INT_MAX ? -1 : table[w][x][y][z];
    }
   
};

結果

Runtime: 20 ms, faster than 99.53% of C++ online submissions for Open the Lock.

Memory Usage: 10.5 MB, less than 99.06% of C++ online submissions for Open the Lock.