今天我們來研究密碼鎖問題，題目是這樣的

有一個四位的密碼鎖，有四個播輪，分別具有0-9 總共10位數字，播輪可以上下旋轉，比如說你可以把”3”轉為”4”或是往另外一個方向轉成”2”，而”0”跟”9”是連在一起的，每次只能旋轉一個播輪．

大概長得如下

現在，我們給定一個目標值target，求出從初始狀態0000轉到這個target的最少次數．

當然，如果只是算出目標值的次數就太簡單了，所以我們要加上另外一個條件．會給上幾組數字，

在轉動的過程中，不可以轉出這幾個數．我們就稱這個限制的數組 DeadEnd 死路．如果轉不出來就直接回傳-1．

舉個例子: DeadEnd是[”1234”,”5678”]，target是0010，那回傳的值就是1，因為只要將第三個播輪播動一下就能夠到達目標數字．

再來個例子:DeadEnd[”8887”, ”8889”, ”8878”, ”8878” , ”8898” , ”8788” , ”8988” , ”7888” , ”9888” ] ，target是“8888”，那答案就是-1，因為所有在target差一位的數字都在DeadEnd中，所以不可能達到target．

所以這題的難點就在怎麼繞過DeadEnd算出最少的轉動次數．

我們先不管所有的限制，不管什麼target或是DeadEnd，先思考一個問題，如果要列出所有的密碼組合，該怎麼做．

先將問題縮小一點，如果我們只轉動一個播盤一次，有幾種可能?

播盤總共有四個，每個都能往上或是往下旋轉，所以總共是4*2 =8種

例如，從 0000開始，分別有1000，9000，0100，0900….，然後同樣的，從這幾個組合開始轉動一次，就能列舉出所有可能．

仔細想想，這個情況可以抽象成一個圖，並且每個節點都是和其他八個節點相連，然後要求出某兩點的最短距離，這不就是典型的BFS問題嗎？

所以我們先寫個粗略版本的演算法如下

fun BFS(target:String):Int{
    val queue: Queue<String> = LinkedList()
    var step = 0
    queue.offer("0000")

    while(queue.isNotEmpty()){
        val size = queue.size
        println("queue size: $size")
        //將目前放在Queue中的所有節點往外擴散 向外尋找
        for(i in 0 until size){
            val currentCode = queue.poll()
            if(currentCode!=null){
                //判斷是否到終點
                println("current code is $currentCode")
                if(currentCode.equals(target)){
                    return step
                }
                for(j in 0 ..3){
                    val up = plusOne(currentCode,j)
                    val down = minusOne(currentCode,j)
                    queue.offer(up)
                    queue.offer(down)
                }
            }
        }
        step++//在這裡增加一步
    }
    return 0
}

fun plusOne(s:String, j:Int):String{//將特定欄位往上撥動
    val ch = s.toCharArray()
    if(ch[j]=='9'){
        ch[j] = '0'
    }else{
        var digital = ch[j].code
        digital++
        ch[j] = digital.toChar()
    }
    return String(ch)
}

fun minusOne(s:String, j:Int):String{//將特定欄位往下撥動
    val ch = s.toCharArray()
    if(ch[j]=='0'){
        ch[j] = '9'
    }else{
        var digital = ch[j].code
        digital--
        ch[j] = digital.toChar()
    }
    return String(ch)
}

這個寫法還有些問題可以加強．

1.會走回頭路，比如說我們從”0000”擴散到”0010”後，在下一個循環“0010”又會擴散回到”0000”，浪費效能去處理已經走過的節點

2.沒有把DeadEnd考慮進去，DeadEnd出現時應該直接跳過不能做任何處理．

不過這些問題也不是特別困難，我們明天會針對這些問題在原有程式碼上做些小小的修改．