是說這題其實還蠻難的= =... 所以就來提供一個簡單的思考方向啦...如果想要自己想的就請忽略這篇文章吧:p ------------------------------------------------------------------------------ 首先釐清問題： 給你一個100*100的迷宮，迷宮裡五種格子：起點、終點、雞排、不可走、可走。 每個可走點都有一個0~9的數字。 雞排則是-10，但是只有第一次走的時候是-10，碰到第二次以後都是0。 現在你要從起點走到終點，希望路上經過的數字和盡量的小。 我們先把問題減化一下，假如現在沒有那個雞排... 那問題就變成： 給你一張地圖，你要從起點走到終點，求數字和最小。 那這個"無雞排問題"要怎麼做呢？ 假設 dis(a,b)代表從位置a到b所經過的數字和的最小值。 那無雞排問題就是要求dis(S,T)的值~~ 那要怎麼求這個dis(S,T)呢@_@? 我們考慮的做法是一種估價的方式。 先假設一開始 dis(S,S) = 0 跟 dis(S,所有除了S以外的格子)都是INF（無限大） 那你應該可以知道 dis(S,S上) dis(S,S下) dis(S,S左) dis(S,S右) 至少有一個是從S直接走過去最短~~ 不過你還不知道是哪個最短，所以就全部走走看wwwww~~~ 因此你可以先把 dis(S,S上) 改成dis(S,S) + map[ S上 ] dis(S,S下) 改成dis(S,S) + map[ S下 ] dis(S,S左) 改成dis(S,S) + map[ S左 ] dis(S,S右) 改成dis(S,S) + map[ S右 ] //是說我先假設都可以走啦= = 不能走就不要走就好了XDrz 如果這四個格子有任何一個的dis被改到是代表什麼意思呢？ 假設被改到的點是P好了 那代表 "原本的dis(S,P)" > dis(S,S) + map[P] 也就是 原本從S到P的最小值不夠小Q_____Q!!! 因為從S走到S再走到P會更小!!! 所以可想而知~ dis(S,P的上下左右) 也有可能是錯的Orz... 沒關係我們學會教訓，繼續從P開始改就是了~~ 因此，我們又可以想到XD，如果對所有的點P，存在一個相鄰的Q使得 dis(S,Q) > dis(S,P) + map[Q] 那我們就可以先把dis(S,Q)設成dis(S,P)+map[Q]，然後繼續更新Q的上下左右。 如果有更新，就繼續做下去~~直到天荒地老...(?) 開玩笑的XD"，直到全部點都不能更新他的四周了，這個時候就是傳說中的穩定狀態了!! 也就是S到所有點的最短路徑都求出來了!!!! Wowwwwwww~ amazing................@_______@! 哦不過不要太高興，問題還沒結束，我們到目前只解決了"無雞排問題" 那"有雞排問題"呢@@!? 其實很簡單啦~~ 因為從S到T的路徑 要馬是經過雞排 要馬是沒經過雞排 有經過雞排是dis(S,B) + dis(B,T) -10 沒經過就是dis(S,T)囉~~ 所以只要 求一次dis(S,任意點) 跟一次dis(B,任意點) 就可以把上面的兩個值都求出來 最後再取最小值就好了:)~ 哦寫這個要注意的是要注意的是map[S,B,T]的值不要亂設>.^ 至於設什麼就自己想啦哇哈哈XDrz~~ 至於這個做法你覺得會不會超過時間或者遞回過深呢~~ 嘿嘿那其實不是現在要討論的問題XD 不過應該是不會啦~~至少我寫是過了= ="。 所以如果沒過大概就是沒看懂我寫的or寫爛了XDrz~~ //不然就是我這篇寫爛了(小聲) --- 先這樣吧...是說我寫得亂七八糟的不知道有沒有人看得懂= =||| 總之有問題再問吧(逃) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.160.236.141 ※ 編輯: math120908 來自: 118.160.236.141 (11/03 23:59)