[轉錄於 ptt2 7-11 in2 ]
(雖然我覺得寫這種文章好像不怎麼合適 :D )
不過話說回來,
這個題目的確有點難(?)
(ㄜ |||| 我是說比起以前啦 :) )
並且, 我想不到怎麼跟別人解釋怎麼作 ^^O
(ㄜ, 因為看到很直覺就寫出來了)
如果真的要說的話,
那我覺得是:
如果發現一個方向 (上/ 下/ 左/ 右) 可以走 (*)
的話, 就走了他 (也就是移動到那個新的位置) 然
後重複一樣的動作 (去看看上下左右能不能走)
而如果發現這一步都不能走 (走到死路裡面了) 則
往回退一格, 在上面那一格嘗試下一個方向.
(*) 其中可以走的定義應該是:
那格可以走 (也就是給定的地圖為一)
以及那格還沒有走過 (避免在 (0, 0) 發現 (1, 0) 可以走後,
走到 (1, 0) 又發現 (0, 0) 可以走而導致無窮的迴圈)
1 1 1
1 0 0
1 1 1
舉個例子, 假設是上面 3x3的圖形, 而我們搜尋的順序是由右邊開始順時針轉:
在 (0, 0) 發現可以往右邊走 -> 走到 (1, 0)
在 (1, 0) 發現可以往右邊走 -> 走到 (2, 0)
在 (2, 0) 發現沒有任何方向可以走 -> 退回
在 (1, 0) 發現也沒有其他的方向可以走 -> 退回
在 (0, 0) 發現還可以往下面走 -> 走到 (0, 1)
在 (0, 1) 發現可以往下面走 -> 走到 (0, 2)
在 (0, 2) 發現可以往右邊走 -> 走到 (1, 2)
在 (1, 2) 發現可以往右邊走 -> 走到 (2, 2)
在 (2, 2) 發現到達終點 -> done :)
--
不過其實也沒有很複雜,
我寫了兩個版本,
一個是透過遞迴的版本 ( 50 lines, 10mins )
一個是將 stack展開的版本 ( 100 lines, ??mins )
--
or如果妳想要看虛擬碼的話, 請按一下空白鍵,
不過我希望妳不要 :)
或是如果你想要看我的程式碼的話, 請透過 browser 連到
http://in.amalea.org/homework/cprog4.c
這會是我 submit 給助教的版本.
不過我希望妳不會在交程式之前來看 :)
(可以先用自己的方式寫完之後, 再來參考別人的作法 :) )
while( 堆疊是不是空的 ){
pop一個點出來 (x, y, 方向)
宣告這一點已經走過了
if( (x, y) 是終點 ){
flag_找到路 = 1;
break;
}
for( ++方向 ; 方向 < 4 ; ++方向 )
if( 這個方向可以走 ){
(x, y, 方向);
(可以走的那個x, 可以走的那個y, -1);
break;
}
if( 沒有加入新的點的話 )
取消這一點已經走過;
}
if( flag_找到路 )
印出路;
else
印出沒有路;
--
「然唯群龍能無首」
-- 放客
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: ntucsb.csie.ntu.edu.tw