問題描述
生物學家要研究一種生活在木頭裡的蟲，主要式統計牠移動時鑽洞的行為模式。現在我們要寫出一個程式來分析資料庫裡牠在每塊木頭中移動過後留下來的洞，來紀錄牠鑽洞的合理路徑。
資料庫裡每個留下來的數據都是由一個 MxN 的矩陣組成，如下圖一為一個5x4 矩陣：
| 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | |||||
| 1 | 0 | * | * | * | 0 | 1 | 0 | * | * | * | 0 | 1 | 0 | 0 | 0 | 0 | ||
| 2 | 0 | * | 0 | * | 0 | 2 | 0 | * | 0 | * | 0 | 2 | * | * | 0 | 0 | ||
| 3 | * | * | 0 | * | 0 | 3 | * | * | 0 | * | 0 | 3 | * | * | 0 | 0 | ||
| 4 | 0 | 0 | 0 | * | * | 4 | 0 | 0 | 0 | * | * | 4 | * | * | * | * | ||
| 圖一 | 圖二 | 圖三 |
在圖一中，蟲鑽出來的洞是填入米號" * "，而沒被鑽過的部份，是填入數字零。圖二是分析圖一後所得到的合理路徑，而為了紀錄精簡，我們只會依順序紀錄「起點、每個轉折點、終點」這三個類型的點的點座標 (x, y)。矩陣座標值從(1, 1)開始。
雖然我們無法得知蟲蟲是從那開始進入木頭的，但因為這種蟲不會回頭走已鑽過的洞，所以在圖二中後，只會得到二種可能路徑，也就是: {(1, 3)、(2, 3)、(2, 1)、(4, 1)、(4, 4)、(5, 4)}，以及 {(5, 4)、(4, 4)、(4, 1)、(2, 1)、(2, 3)、(1, 3)}，以上二種。
因為蟲洞都不會相連，如圖三。所以每個蟲洞數據都只能被分析出二種可能路徑。請寫出一個程式來算出蟲蟲的鑽洞路徑。
第一行先輸入蟲洞矩陣大小，先輸入 M 再輸入N，中間以空格隔開。
接著逐行輸入每一列的蟲洞數據，"*"代表蟲洞，"0"代表木頭，等輸入N 行數據後，則輸入自動結束，產生輸出。
註：M 及N 為介於3~20 的正整數。{原題為3~10，此處改為20)
依蟲蟲行進方向，逐行輸出路徑上的「起點、每個轉折點、終點」這三個類型的各點點座標x y，中間以空格隔開。只需輸出二種可能路徑的其中x y較小的為起點的一種路徑即可。 {x較小或x相等y較小}
5 4 0***0 0*0*0 **0*0 000**
1 3 2 3 2 1 4 1 4 4 5 4
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||