原文链接：http://www.mydrs.org/program/list.asp?id=334
〖题目描述〗给定m
n方格，某些方格内不可通行，求左上到右下最短路。〖基本算法〗
本题使用动态规划求解。
记f（x，y）为从（0，0）走到（x，y）的最短路的长度，有
f（x，y）= min {f（i，j）+ sqrt（sqr（x-i）+ sqr（y-j）），格子（i，j）不在（x，y）右或下方且可直达}；
特别的，f（0，0）= 0；
算法的复杂度为O（m^3
n^3）。〖优化〗
上面这个算法是极其浪费的。事实上，可以很容易证明，如果一条路径有一个"拐弯"的地方不是某个障碍的左下或右上角，这条路一定不是最短路（下图）。所以我们可以对动态规划算法做个优化：
f（x，y）= min {f（i，j）+ sqrt（sqr（x-i）+ sqr（y-j）），格子（i，j）不在（x，y）右或下方且可直达且格子（i，j）位于某个障碍的左下或右上角}；
另外我们只对障碍左下或右上角的格点及终点求f（x，y）。
这样改进以后算法的复杂度为O（m
n w^2）（w为障碍数），时间效率是很高的了。当然，本题还有很多优化方法，比如旋转坐标轴，然后仅对"最近的"障碍扫描等等，同学们可以自己试试看。
作者：林元
来源：福州第一中学
时间：2002-03-23
上一篇：NOIP2001普及组获奖名单
下一篇：SGOI7《积木搭建问题》