是说这题其实还蛮难的= =... 所以就来提供一个简单的思考方向啦...如果想要自己想的就请忽略这篇文章吧: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)