---

這個題目有學過演算法的朋友一定是直覺的使用BFS

或者可能會想到用mazing problem

也就是當8個方位都找沒路時

再從stack之中pop out

back tracking原來的位置

如果我沒學過演算法

可能就會試著用這樣的方式了吧

如果本題不是用BFS

應該蠻具趣味與挑戰性的 

 

**********************************************

 

這裡可以將迷宮的每個點視作節點

如下圖所示

###

. . .

###

第一個點"."代表有路

而第二個點與第一個點在相鄰的位置

所以這兩個節點的位置可以視作為1

若繼續觀察可以發現任兩個相鄰"有路"節點

之間的距離都是固定的1

又相鄰節點也沒有特定的方向

所謂"特定的方向"就是例如A->B只能是A節點走到B節點

但不能從B走回A

所以這一題直覺上就是使用BFS

也就是說

1.想要找無方向

2.無權重(或權重皆相同的邊)

某節點到某節點之間最短距離

就要使用BFS

DFS可以用在檢查有沒有迴路

或是DAG的拓譜排序法上

又或是找強連通圖上

 

*********************************************

 

若有了這個基礎

剩下的工作就是將BFS以使用的程式語言翻譯好即可

以Python為例

可以直接使用內部建立好的queue

宣告q是一個queue

則 q = queue.Queue(maxsize=num)

注意第二個queue是大寫"Q"

 

*********************************************

我們動手尋訪BFS

可以發現先進入queue的節點

其子點會比晚進入的節點之子點來的早被尋訪

一位來自知名補習班教授"資料結構"的老師

有一個口訣叫做"伯伯的兒子比叔叔的兒子先"

很生動的描述BFS尋訪的過程

若將祖父位置的節點與父親還有兒子節點一層層的分好

會有"三代不同堂"的現象發生

也就是說queue任何時間點最多只會有兩代同堂的情況

 

*********************************************

Lemma 22.3

Suppose that during the execution of BFS on a graph G , the queue Q

contains the vertices (v[1],v[2],...,v[r]) , where v[1] is the head of Q and v[r] is the tail.

Then, v[r].d <= v[1].d + 1 and v[i].d <= v[i+1].d for i = 1,2,3,....,r-1

 

(引自Cormen的"introduction to algorithms")

有興趣的朋友可以試試看證明