一道简单的算法题

Question

给定起点坐标(x0,y0)和终点坐标（x1,y1),其中x0,y0,x1,y1为整数且，x0<x1,y0<y1,假设从起点出发，每次只能沿x正方向或者y正方向走一个单位距离，请编程实现从起点到终点的所有路径
例如起点(0,0)终点（1，1）
路径如下：
（0，0）（0，1）（1，1）
（0，0）（1，0） （1，1）

………………………………………………………………………………………………………………………………
我说下我当时的思路，从终点往前推一步，要么从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)，不过那个优化我就不在这里讲了，你可以看看这篇文章。

Answer 2

#include <iostream>
#include <vector>

using namespace std;
typedef struct _node {
    int x, y;
}Node;
vector<Node> stack;
int ss[100][100];
int x1,y1;
int dfs(int x, int y) {
    int xx,yy;
    if (x == x1 && y == y1) {
        int i;
        int size = stack.size();
        for (i = 0; i < size; i ++) {
            printf("(%d,%d) ", stack[i].x, stack[i]. y);
        }
        printf("\n");
    } else {
        if (x + 1 <= x1) {
            xx = x + 1;
            yy = y;
            if(!ss[xx][yy]) {
                Node n;
                n.x = xx;
                n.y = yy;
                ss[xx][yy] = 1;
                stack.push_back(n);
                dfs(xx, yy);
                ss[xx][yy] = 0;
                stack.pop_back();
            }
        }

        if (y + 1 <= y1) {
            xx = x;
            yy = y + 1;
            if(!ss[xx][yy]) {
                Node n;
                n.x = xx;
                n.y = yy;
                ss[xx][yy] = 1;
                stack.push_back(n);
                dfs(xx, yy);
                ss[xx][yy] = 0;
                stack.pop_back();
            }
        }

    }
}
int main() {
    int x,y;
    scanf("%d%d", &x, &y);
    scanf("%d%d", &x1, &y1);
    Node n;
    n.x = x;
    n.y = y;
    stack.push_back(n);
    dfs(x,y);
    return 0;
}

input :
0 0
3 3
output:
(0,0) (1,0) (2,0) (3,0) (3,1) (3,2) (3,3)
(0,0) (1,0) (2,0) (2,1) (3,1) (3,2) (3,3)
(0,0) (1,0) (2,0) (2,1) (2,2) (3,2) (3,3)
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (3,3)
(0,0) (1,0) (1,1) (2,1) (3,1) (3,2) (3,3)
(0,0) (1,0) (1,1) (2,1) (2,2) (3,2) (3,3)
(0,0) (1,0) (1,1) (2,1) (2,2) (2,3) (3,3)
(0,0) (1,0) (1,1) (1,2) (2,2) (3,2) (3,3)
(0,0) (1,0) (1,1) (1,2) (2,2) (2,3) (3,3)
(0,0) (1,0) (1,1) (1,2) (1,3) (2,3) (3,3)
(0,0) (0,1) (1,1) (2,1) (3,1) (3,2) (3,3)
(0,0) (0,1) (1,1) (2,1) (2,2) (3,2) (3,3)
(0,0) (0,1) (1,1) (2,1) (2,2) (2,3) (3,3)
(0,0) (0,1) (1,1) (1,2) (2,2) (3,2) (3,3)
(0,0) (0,1) (1,1) (1,2) (2,2) (2,3) (3,3)
(0,0) (0,1) (1,1) (1,2) (1,3) (2,3) (3,3)
(0,0) (0,1) (0,2) (1,2) (2,2) (3,2) (3,3)
(0,0) (0,1) (0,2) (1,2) (2,2) (2,3) (3,3)
(0,0) (0,1) (0,2) (1,2) (1,3) (2,3) (3,3)
(0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (3,3)