如何根据条件计算3d网格中从一个点到另一个点的所有路径

Question

给出输入xm，ym，h，我必须在3d网格中找到从点（1,0,1）到（xm，ym，1）的所有路径，例如：

1. （x，y，z）的可能移动是（x + 1，y，z），（x + 1，y + 1，z），（x + 1，y-1，z）

2. 如果z

3. 如果z> 1个其他可能的移动也是（x + 1，y，z-1），（x + 1，y + 1，z-1），（x + 1，y-1，z- 1）

我想出了一种适用于z = 1的算法，但是我不确定如何使其适用于z的其他值。任何帮助将不胜感激。

llong countPaths3(int xm, int ym, int h) {
    std::pair<int,int> pair1 = {1,0};
    std::map<std::pair<int,int>, llong> map1;
    map1.insert({pair,1});
    int starty = -1;
    int endy = 1;
    llong value = 0;
        for(int x = 2; x <= xm; x++) {
            for(int y = starty; y <= endy; y++)
            {
                if (map1.count({x, y}) == 0) {
                    value = map1[{x - 1, y}] + map1[{x - 1, y + 1}] + map1[{x - 1, y - 1}];
                }

                map1[{x, y}] = value;
            }
            starty--;
            endy++;
        }
        return map1[{xm,ym}];
}

Answer 1

虽然此问题可以组合解决，也可以使用Dynamic Programming解决，但时间和内存复杂度为O(xm * ym * h)。

考虑一个3d数组，其中数组索引i, j, k上的每个点代表从(1, 0, 1)到(i, j, k)的获取方法的数目，我们想在索引(xm, ym, 1)处找到该值。

我们需要开始填充数组，首先填充x = 1层，除了(1, 0, 1)的值为1外，有0种方法可以到达任何地方。第二个填充x = 2层，除了(2, 0, 1)，(2, 1, 1)，(2, 0, 2)的值为1外，有0种方法可以到达任何地方。然后填充下一层以及上一层，依此类推，直到到达第xm层-至此，您已经完成了。填充索引(i, j, k)的一般公式为：

A[i, j, k] = 
A[i-1, j-1, k-1] + A[i-1, j-1, k-1] + A[i-1, j-1, k-1] + 
A[i-1, j, k]     + A[i-1, j, k]     + A[i-1, j, k]     + 
A[i-1, j+1, k+1] + A[i-1, j+1, k]   + A[i-1, j+1, k+1]

如上所述-使用此公式填充数组需要花费时间和内存复杂度O(xm * ym * h)。

不要忘记检查边缘情况并手动填充第一层。

祝你好运。>>