#48 老鼠走迷宮 (mouse maze)

在大學的資料結構的課程裡,大約在教過 Stack, Queue 和 List 這些基本的資料結構之後會有一個老鼠走迷宮的作業.這份作業說難不難,說簡單也沒那麼簡單,對一個正在學習資料結構的學生來說,花個一兩個晚上來寫這份作業是很正常的.如果寫程式正是你的工作,而且你以前沒念過資料結構的話,不妨試著做做看這份作業.

老鼠走迷宮的內容是,要隨機產生一個矩陣,矩陣的大小最好由使用者輸入設定的.然後在矩陣裡的每個位置也會隨機產生三種不同的地形,例如平地,河流與高山.你可以再設計其他不同的地形,老鼠在每一個地形上走動時會花費不同的體力,例如平地是 1 ,河流是 2,而老鼠是無法穿越高山.老鼠的出發點是矩陣的左上角,也就是 (0,0) 的位置, 然後終點在右下角,也就是 (n,m) 的位置,n,m 代表的是矩陣的兩個邊長.

你所要寫的程式是讓使用者輸入矩陣的大小,然後為矩陣的每一個格子隨機產生地形,接著老鼠從出發點開始移動,看看老鼠是否可以走到終點.因為地形中會有高山,所以老鼠不一定都會有一條路可以走到終點.然而,老鼠能走的路也可能不只一條能到終點,你可以試著找出一條就行了.

整個題目的重點在於兩個地方.第一,移動的方向要定出一套規則,第二,要能夠記錄走過的路跡.移動方向的規則可以用最簡單的方式來實行,除了在邊邊與角落以外的格子,每個格子都可以有八種移動方向,上,下,左,右,左上,左下,右上,右下.每到達一個格子時,就可以依照固定的順序來移動到下一個格子,如果在下一個格子都沒有路走或是每個方向都試過了,那就回到上一個格子.因此,路跡的記錄是很重要的,因為需要回到上一個格子.

以下我提供十多年前寫的版本



如果你順利寫完之後,還有一個延伸題目給你繼續挑戰,那就是如果有多條可以走的路跡時,列出最省力的路跡.這延伸題目就不是那麼簡單了,未來再來寫篇文章來討論.


Share:

0 意見:

張貼留言