[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, 0...