先看題目：

你有一個帶有四個圓形撥輪的轉盤鎖。每個撥輪都有10個數字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。 每個撥輪可以自由旋轉：例如把 '9' 變為? '0'，'0' 變為 '9' 。每次旋轉都只能旋轉一個撥輪的一位數字。鎖的初始數字為 '0000' ，一個代表四個撥輪的數字的字符串。列表 deadends 包含了一組死亡數字，一旦撥輪的數字和列表里的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉。字符串 target 代表可以解鎖的數字，你需要給出最小的旋轉次數，如果無論如何不能解鎖，返回 -1。例子1： 輸入：deadends = ["0201","0101","0102","1212","2002"], target = "0202" 輸出：6 解釋： 可能的移動序列為 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。 注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 這樣的序列是不能解鎖的， 因為當撥動到 "0102" 時這個鎖就會被鎖定。例子2： 輸入: deadends = ["8888"], target = "0009" 輸出：1 解釋： 把最后一位反向旋轉一次即可 "0000" -> "0009"。

在做隊列的專項的時候遇到，思考了20分鐘左右無任何方案，搜了B站花花醬的視頻講解才搞懂(https://www.bilibili.com/video/av31636797?t=385)。

這道題算是典型的無向圖問題，每個數字表示圖中一個節點，"0000"表示根節點，每個節點由四位數組成，其中每個數每次轉動存在兩種變形，所以一次轉動，節點有八個子節點，如下圖：

?將待遍歷的節點添加到隊列中，遍歷完成，則將節點添加到死節點數組中。從圖中可看出，第一次遍歷有八種可能，如果某個節點和目標節點相等，則返回當前深度即可，不等的話，如果沒有訪問過它或者死節點數組中沒有它，即我們需要去遍歷它的子節點，這時候將它加入到隊列里，以待訪問它的子節點。同時將它加入到死節點數組中，防止后續重復訪問該節點。因為遍歷每一層的時候，都會更新隊列，所以一開始就要知道每層遍歷的數量。c語言不像其它高級語言，有現成的隊列結構拿來使用，需要自己實現，此外，死節點數組使用了哈希數組，因為每個節點都是10000以內的一個數字，如果使用strcmp的話耗時可能更久。

下面是c代碼的解法，只看最下面的核心函數即可，前面代碼時關于隊列和哈希表的，可略過：

/* BFS求解 */#define MAX 10001//循環隊列 struct queue {int head, end, length;char a[10001][5]; };//入隊 int enQueue(struct queue *q, char *n) {if (q->length >= MAX - 1)return -1;else{strcpy(q->a[q->end], n);q->end = (q->end + 1) % MAX;q->length++;return 0;} }//出隊 int deQueue(struct queue *q, char *n) {if (q->length == 0)return -1;else{strcpy(n, q->a[q->head]);q->length--;q->head = (q->head + 1) % MAX;}return 0; }//獲取隊列長度 int queueLength(struct queue *q) {return q->length; }//判斷隊列是否為空 int isQueueEmpty(struct queue *q) {if (q->length == 0)return 1;elsereturn 0; }//判斷t是否在head中 int inDead(int *dead, char *t) {int i, v;for (i = 0, v = 0; i < 4; i++)v = v * 10 + (t[i] - '0');if (dead[v] == 1)return 1;elsereturn 0;}//添加到哈希隊列中 void enDead(int *dead, char *t) {int i, v;for (i = 0, v = 0; i < 4; i++)v = v * 10 + (t[i] - '0');dead[v] = 1;return ; }int openLock(char ** deadends, int deadendsSize, char * target){int i,j,k, ret, len, steps = 0;char start[] = "0000", n[5] = {0}, curr[5] = {0};struct queue *q;q = (struct queue *)malloc(sizeof(struct queue));if (!q) exit(1);q->length = q->head = q->end = 0;int dead[10000] = {0};for (i = 0; i < deadendsSize; i++)enDead(dead, deadends[i]);if (inDead(dead, start))return -1;enQueue(q, start);while(!isQueueEmpty(q)){++steps;len = queueLength(q);for (k = 0; k < len; k++){deQueue(q, curr); for (i = 0; i < 4; i++){for (j = -1; j < 2; j+=2){strcpy(n, curr);n[i] = (n[i] - '0' + j + 10)%10 + '0';if (!strcmp(n, target)) return steps;if (inDead(dead, n)) continue;enQueue(q, n);enDead(dead,n);}}}}return -1; }

參考資料：

1.?https://www.bilibili.com/video/av31636797?t=385

=============================================================================================

Linux應用程序、內核、驅動開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的leetcode 752. 打开转盘锁 c代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。