推 ianlini:從 如果這四個格子有任何一個的dis被改到是代表什麼意思呢 11/04 00:13
→ ianlini:這行....開始看不懂(倒 11/04 00:13
推 skyly:應該就字面上的意思吧 其中一個相鄰的格子被該格更新這樣 11/04 00:14
推 xluds24805:推~~我也是這樣子寫的丫...結果只有二分>口<"" 11/04 00:17
推 williamiced:大推 11/04 18:14
是說這題其實還蠻難的= =...
所以就來提供一個簡單的思考方向啦...如果想要自己想的就請忽略這篇文章吧: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)