b545: 1.蟲蟲鑽洞問題
Tags :
Accepted rate : 28人/30人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-09-15 01:06

Content

問題描述
生物學家要研究一種生活在木頭裡的蟲,主要式統計牠移動時鑽洞的行為模式。現在我們要寫出一個程式來分析資料庫裡牠在每塊木頭中移動過後留下來的洞,來紀錄牠鑽洞的合理路徑。
資料庫裡每個留下來的數據都是由一個 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 *   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)},以上二種。
因為蟲洞都不會相連,如圖三。所以每個蟲洞數據都只能被分析出二種可能路徑。請寫出一個程式來算出蟲蟲的鑽洞路徑。

 

Input

第一行先輸入蟲洞矩陣大小,先輸入 M 再輸入N,中間以空格隔開。
接著逐行輸入每一列的蟲洞數據,"*"代表蟲洞,"0"代表木頭,等輸入N 行數據後,則輸入自動結束,產生輸出。
註:M 及N 為介於3~20 的正整數。{原題為3~10,此處改為20)

Output

依蟲蟲行進方向,逐行輸出路徑上的「起點、每個轉折點、終點」這三個類型的各點點座標x y,中間以空格隔開。只需輸出二種可能路徑的其中x y較小的為起點的一種路徑即可。 {x較小或x相等y較小}

Sample Input
5 4
0***0
0*0*0
**0*0
000**
Sample Output
1 3
2 3
2 1
4 1
4 4
5 4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
出處:
102學年度北基區北三區資訊學科能力競賽 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」