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