題目：http://poj.org/problem?id=3083
迷宮遊戲存在一種找路的策略，叫左手法則(或右手法則)
意即行走選路完全依據「牆壁靠左手邊」的原則
當然，只有入口和出口都在迷宮邊邊的時候才有效、這裡保證都找得到路
給一個w*h(40*40)的迷宮、有一些障礙物
問左手法則會走幾步？右手法則走幾步？最佳路線會走幾步？
(推薦這題!)
程式碼：http://codepad.org/nwXAqKYN
最佳路線的部分就是傳統的迷宮問題
非常適合訓練速度的題目，看你能不能把左手法則簡單漂亮的實現出來
首先直覺上左手和右手循路的旋轉方向應該是相反的
我們試著把它寫成同一個函式就好
拿左手法則來說，一個可行的尋路方式是這樣的：
1.定義一開始面對的方向
2.從左手邊的方向(面對向逆時針1次)開始檢查，看能不能走
3.依次檢查左手邊、正前方、右手邊、背後這四個方向(左手邊向順時針k次，k=0...3)
只要能走就走
4.更新目前的方向、檢查是否已經到達終點
右手法則同理，順/逆時針對調
由於左手/右手法則走出來路的可能性是唯一的
所以不必開queue處理狀態、直接每次代換現在走到哪就好
沒有留言:
張貼留言