折线的解题报告

　　　　　　　　福州第一中学 林 元

〖题目描述〗
　　给定mn方格，某些方格内不可通行，求左上到右下最短路。

〖基本算法〗
　　本题使用动态规划求解。
　　记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为障碍数），时间效率是很高的了。
　　当然，本题还有很多优化方法，比如旋转坐标轴，然后仅对"最近的"障碍扫描等等，同学们可以自己试试看。