讓我們來針對昨天留下的問題，來修改一下程式碼．把DeadEnd考慮進去，並且不要走回頭路．

fun BFSWithDeadEnds(deadEnds:Array<String>,target:String):Int{
    //記錄要略過的DeadEnd
    val deadMap = mutableSetOf<String>()
    for(element in deadEnds){
        deadMap.add(element)
    }
    //記錄走過的節點
    val visited = mutableSetOf<String>()

    val queue: Queue<String> = LinkedList()
    var step = 0
    queue.offer("0000")
    visited.add("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) {
                if( deadMap.contains(currentCode)){//判斷是否在DeadEnd中
                    continue
                }
                if(currentCode.equals(target)){ //判斷是否到終點
                    return step
                }

                for(j in 0 ..3){
                    val up = plusOne(currentCode,j)
                    if(!visited.contains(up)){
                        queue.offer(up)
                        visited.add(up)
                    }
                    val down = minusOne(currentCode,j)

                    if(!visited.contains(down)){
                        queue.offer(down)
                        visited.add(down)
                    }
                }
            }
        }
        step++//在這裡增加一步
    }
    return -1
}

我們多增加了DeadEnd的Map來記錄哪些不能經過，又增加了一個visted來記錄哪些我們已經走過了，如果在DeadEnd中有的我們就跳過，在visted中有的我們下次就不會再走重複的路，而這兩種都是String來記錄的，所以可以把兩個Map合併起來，這部分就交給各位了．

BFS的基礎到這邊就結束了，但是我們可以聊聊一點進階的．雙向BFS

雙向BFS

基礎的BFS從起點開始，一路往外擴張路徑，一直到找到終點為止，從頭到尾終點都沒有移動或改變過．

讓我們換個角度，如果在我們從起點往外擴大的時候，終點也遵循相同模式往外擴大，當兩邊擴張的的節點碰在了一起，就是得到正確解答的時候．前半部的路徑，就是由起點到達目前相遇的節點的路徑，而後半段的路徑，就是由相遇節點到終點的路徑．雖然時間複雜度沒有改變，但是在實際上，所搜尋的路徑只有全部搜尋的一半．更加有效率．

不過，雙向BFS也是有前提的，就在”從終點往外擴大”，如果一開始不知道終點是哪一個的話，自然也不能從終點開始擴大，例如我們前幾天的例子，最矮的二元樹，由於不知道哪個葉節點才是最終解答，因此自然不能使用雙向BFS．

不過我們的密碼鎖問題，題目知道我們要尋找的終點，就能使用雙向BFS

fun BFSWith2Way(deadEnds: Array<String>, target: String): Int {
    //記錄要略過的DeadEnd
    val deadMap = mutableSetOf<String>()
    for (element in deadEnds) {
        deadMap.add(element)
    }
    //記錄走過的節點
    val visited = mutableSetOf<String>()

    var setFromStart = mutableSetOf<String>() //利用Set取代Queue 可以快速判斷是否存在某個元素
    var setFromEnd = mutableSetOf<String>()
    var step = 0
    setFromStart.add("0000") //定下起點
    setFromEnd.add(target) //定下終點
    visited.add("0000")
    while (setFromStart.isNotEmpty() && setFromEnd.isNotEmpty()) {
        //往外擴散的過程中，不能夠直接修改set內容 所以改用temp來儲存擴散結果
        val temp = mutableSetOf<String>()
        for(currentNode in setFromStart){
            if(deadMap.contains(currentNode)){
                continue
            }

            if(setFromEnd.contains(currentNode)){
                return step
            }
            visited.add(currentNode)

            for (j in 0..3) {
                val up = plusOne(currentNode, j)
                if (!visited.contains(up)) {
                    temp.add(up)
                }
                val down = minusOne(currentNode, j)
                if (!visited.contains(down)) {
                    temp.add(down)
                }
            }
        }
        step++//在這裡增加一步
        //這邊交換setFromStart setFromEnd 下一輪會從setFromEnd開始擴散
        //利用temp保存現在的setFromStart
        setFromStart = setFromEnd
        setFromEnd = temp
    }
    return -1
}

其實實際上還是那套BFS，只是不使用Queue而使用Set，就能更加快速判斷兩個集合是否有交集，有了交集就代表找到答案了．

另外一個小技巧就是在while最後交換兩個Set，這樣兩邊就能夠輪流擴散…

說到這個，其實還能小小優化一下，可以在一開始時做一個判斷兩個set的大小，然後擴散小的那個，這樣可以稍稍壓縮使用的空間，佔用的空間成長也會慢上一些，效率會高上一點點

不過不管是單向還是雙向，或是有沒有進行最佳化，從Big O的角度來看，所佔用的空間複雜度都是一樣．所以還是先熟悉BFS的基本就可以啦．