輸入：deadends 是指針終止狀態列表，target 是希望到達的指針狀態，初始化指針狀態是0000。
輸出：如果指針能夠到達target狀態，則變化的最少步驟是多少。如果不能到達target狀態，返回-1。
分析：指針的狀態有0000，0001，… 9999 ，1萬種狀態。可以看做是1萬個節點。
　　每個狀態之間如果只有一個位置上的值有變化，則這兩個狀態之間有連線。例如節點0000，和1000，0100，0010，0001，9000，0900…等這些節點有聯系。
　　每個節點上的每一個位置有三種操作：減1，不變，加1。
　　解決思路就是按照BFS的標準思路。先處理0000節點，接著處理與其相鄰的節點，再依次擴散出去。
　　本題目很影響效率的地方是節點一個位置坐加1，建1的操作變化。
　　直接操作字符串，沒有問題，只是會慢。

//變換for(int j=0;j<4;j++){int val = node.charAt(j)-48;int newVal = (val==9?0:val+1);int newVal1 = (val==0?9:val-1);String newNode = node.substring(0,j)+newVal+node.substring(j+1);if(!set.contains(newNode)){queue.offer(newNode);set.add(newNode);}String newNode1 = node.substring(0,j)+newVal1+node.substring(j+1);if(!set.contains(newNode1)){queue.offer(newNode1);set.add(newNode1);}}

還有一種思路是用二進制來做。鏈接。
　　 對于節點node=“1234”，先轉為int。這個int有效位數是16位。這個int是這樣的：
　　　0001 0010 0011 0100 ，依次表示1，2，3，4。
　　　如果需要將2變為3，則可以進行如下操作：

int mask = (1 << 4) - 1;int[] num = new int[]{(nodeInt >> 12) & mask,(nodeInt >> 8) & mask,(nodeInt >> 4) & mask,nodeInt & mask};num[1] +=1;int res = 0;for (int i = 0; i <4 ; i++) {res <<= 4;res |= num[i];}

先使用掩碼mask，把nodeInt的值分成4個值放到數組中。接著修改某一位置的值。最后再通過移位，做異或操作成為新的狀態。這樣速度就快很多。
代碼

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【Breadth-first Search 】752. Open the Lock的全部內容，希望文章能夠幫你解決所遇到的問題。

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