How to count all paths from a point to another point in 3d grid with conditions

Question

Given the input xm, ym,h I have to find all paths from point (1,0,1) to (xm, ym, 1) in a 3d grid such as:

1. possible moves from (x,y,z) are (x+1, y, z), (x+1, y+1, z), (x+1, y-1, z)

2. if z < h more possible moves are (x+1, y, z+1), (x+1, y+1, z+1), (x+1, y-1, z+1)

3. if z > 1 more possible moves are also (x+1, y, z-1), (x+1, y+1, z-1),(x+1, y-1, z-1)

I figured out an algorithm that works for z = 1, but I am not sure how to make it work for other values of z. Any assistance will be appreciated.

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

While this problem can be solved combinatorially it can also be solved using Dynamic Programming, with a time and memory complexity of O(xm * ym * h).

Consider a 3d array where each point at index i, j, k in array represents the number of ways to get from (1, 0, 1) to (i, j, k), we would like to find the value at the index (xm, ym, 1).

We need to start filling the array,
First fill the x = 1 layer, there are 0 ways to get everywhere except for (1, 0, 1) which has the value of 1.
Second fill the x = 2 layer, there are 0 ways to get everywhere except for (2, 0, 1), (2, 1, 1), (2, 0, 2) which has the value of 1.
Than fill the next layer, and the one above it and so on until you reach the xmth layer - at this point you are done.
The general formula to fill up the index (i, j, k) is:

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]

As mentioned - filling up the array using this formula takes time and memory complexity of O(xm * ym * h).

Don't forget to check edge cases and fill the first layer manually.

Good luck.