上上篇文寫太爛了，連我自己都看不太懂，所以就重新寫一篇... 希望比較容易看得懂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