一道简单的算法题

Question

给定起点坐标(x0,y0)和终点坐标（x1,y1),其中x0,y0,x1,y1为整数且，x0………………………………………………………………………………………………………………………………我说下我当时的思路，从终点往前推一步，要么从x轴走到终点要么从y轴走向终点，然后依次类推。

Answer 1

这真的能算算法题吗。。你要求都是所有路径了，那就是要遍历了。遍历你不管是正着想还是倒着想复杂度应该都是一样的。更新：你的想法是可以的，用一个简单的递归就好。当开始和结束有一个轴一样且另一个轴之差1的时候，你就把返回一个路径集，只包含一个路径：（开始点，终点）。比如开始：(0,0)，结束：(0,1)，就返回{{(0,0),(0,1)}}。开始(0,0)，结束(1,0)的话就是{{(0,0),(1,0)}}。如果不能一步走到，就拿该点左边所有路径的集合，给每一个路径结尾加上当前点，该点下面的所有路径结尾也加上当前点，然后合在一起。比如开始：(0,0)，结束：(1,1)，就拿左边的结果加上当前点，也就是{{(0,0),(0,1),(1,1)}}，和下面的结果加上当前点，也就是{{(0,0),(1,0),(1,1)}}，合成一个集合，也就是{{(0,0),(0,1)},{(0,0),(1,0)}}。当然这样会有很多重复的计算，比如你算从(0,0)到(5,5)的时候会算2次(4,4)，以及很多很多次(1,1)，不过那个优化我就不在这里讲了，你可以看看这篇文章。