推 a123zyx:我覺得郭好可愛 11/04 19:42
推 ianlini:我一開始做法就是第一個XD 11/04 19:46
推 williamiced:謝謝你摟熱心助人 11/04 20:38
上上篇文寫太爛了，連我自己都看不太懂，所以就重新寫一篇...
希望比較容易看得懂Q_Q。
---
我們只考慮這個無雞排問題。
我們可能有一種很簡單的想法就是:
假設一個Function(x,y)會回傳點(x,y)走到終點的最小數字和~
那有一個很簡單的遞迴式是
if(x==Gx && y==Gy) Function(x,y) = 0;
others,
/ Function(x+1,y)
/ Function(x-1,y)
Function(x,y) = map[x,y] + min {
\ Function(x,y+1)
\ Function(x,y-1)
當然這樣很明顯會可能出現
Function(x,y) => Function(x,y+1) => Function(x,(y+1)-1)
=> Function(x,y+1) .....一直重複下去>"<
所以就很明顯的會爆炸啦XD
解決方法就是紀錄一下在目前所走路徑上的格子不會再被走到
意思是對於某個遞迴關係Function(x1,y1) => ... => Function(x2,y2)
不存在x1==x2, y1==y2。
但是呢!! 這樣貌似不會全部過>.^ 而且好像第二筆測資就跑不出來了喔QQ
所以我們要嘗試改進這個算法:
反過來求起點到終點得最小值@_@
我們定義dis(Px,Py)代表從起點到P所經過的數字和的可能最小值~
就是可以對任意的P去嘗試改進他附近的點
也就是dis(Px,Py) 嘗試推到 dis(Px,Py+1)
dis(Px,Py-1)
dis(Px+1,Py)
dis(Px-1,Py)
這四個位置有任何一個位置可以被改的條件是（假設是要改(Px,Py+1)）
dis(Px,Py+1) > dis(Px,Py) + map[Px,Py+1]
意思就是說"原本以為到(Px,Py+1)的最小值"其實不是最小
因為經過(Px,Py)再走到(Px,Py+1)會比較小。
所以啦...想當然爾~因為dis(Px,Py+1)原本的值並不是最小值
因此(Px ±1,Py+1 ±1)也都有可能不是最小值。
所以就繼續遞迴下去，從(Px,Py+1)去改他四周的dis值。
然後就一直修正現在點上下左右的值，如果可以修正就往那個點繼續修正～
一直到沒東西可以修正就win啦哇哈哈哈>.^
至於起始值嗎，一開始就假設全部都走不到dis(Px,Py) = INF
除了起點有dis(Sx,Sy) = 0。
然後從起點開始對旁邊更新就好了:)
範例請參考上一篇~~~
大概就這樣XD"
敘述不清楚真是抱歉>"<\\\
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.82