Print All Number Grid Paths

[Everlong]

I need some help with a project. I'm trying to print out all possible combinations of a number grid.

For example:

1 3 2 5 4
2 4 3 1 5
5 3 4 2 3
4 3 1 5 2
5 3 4 1 2

The numbers are randomly generated. You start at the top of each column and then can either move down or diagonally down until you reach the bottom of any column. I need to find all of the possible number combinations. I'm stumped, any ideas?

The numbers would probably be passed into the function as an array of nodes. And these nodes contain pointers to each of its 3 childs (center, left, and right) and its respective int value.

[ArkM]

Use the classic recursive solution approach.

Suppose you (your traverse algorithm, of course) are standing at the position (i,j) - level i (from 0 to m-1, up to bottom) column j (from 0 to n-1, left to right). That's a current point of your downward traversal, print it. Now you have possible down ways:
- 0 if j == m-1, end of traversal.
- 2 if j == 0 or j == n-1 (n > 1)
- 3 if j > 0 && j < n-2 (n > 2)
Make all possible steps (let the same algorithm continues).

At every point you have selected all possible unique downward ways. Now start this algorithm for every cell of the level 0. All done, you have printed all possible downward grid traversals...

No need in pointers, use a grid matrix directly.

[Everlong]

Thanks! Here is my code:

#include <iostream>

using namespace std;

void printGrid(int grid[3][3], int i, int j, int n) {
    cout << grid[i][j];
    if ( i == n - 1 ){
        cout << endl;
        return;
    }
    if( j == 0 || j == n - 1){
        if(j == 0){
            printGrid(grid, i + 1, j, n);
            printGrid(grid,i + 1, j + 1, n);
        }
        if (j == n - 1){
            printGrid(grid,i + 1,j, n);
            printGrid(grid,i + 1, j - 1, n);
        }
    }
   else{
       if( j > 0 && j < n - 2){
            printGrid(grid,i + 1,j, n);
            printGrid(grid,i + 1, j + 1, n);
            printGrid(grid,i + 1, j - 1, n);
       }
   }
}

int main(){
    int maze[3][3] = {{'1', '3', '2'},{'3', '2', '1'},{'2', '2', '3'}};
    int x = 3; //Width and height of array
    printGrid(maze, 0, 0, 3);
    return 0;
}

However, my ouput is:

495150
50
50

and I've reviewed my code and can't find what is wrong.

[ArkM]

Well, we have three defects: the first one is mine, the others are yours ;)
#2: the int array maze is initialized by char data but is printed as int. The 1st 49 is (int)'1' (ASCII code of '1')...
#3: You ignored start this algorithm for every cell of the level 0 phrase...

#1: More seriously (mea culpa;) ) - we must repeat the printing of every cell on every path. For example, at cell i,j we must reprint all previous traversed cells for every downward paths. So we need some kind of path memory to print the path when the lowest level achieved.

That's my alg correction (try to improve it):

void Traverse(const int* pij, int i, int j, int m, int n, int* path)
{
    path[i++] = *pij;   // i => the next level
    if (i == m) {       // lowest level
        for (int k = 0; k < m; ++k) {
            if (k) cout << ' ';
            cout << path[k];
        }
        cout << '\n';   // path printed
    }
    else if (j == 0) {
        Traverse(pij+n,i,j,m,n,path);
        Traverse(pij+(n+1),i,j+1,m,n,path);
    } else if (j == n - 1) {
        Traverse(pij+(n-1),i,j-1,m,n,path);
        Traverse(pij+n,i,j,m,n,path);
    } else {
        Traverse(pij+(n-1),i,j-1,m,n,path);
        Traverse(pij+n,i,j,m,n,path);
        Traverse(pij+(n+1),i,j+1,m,n,path);
    }
}
/// Non-recursive starter (loop for the 1st row):
void TraverseGrid(const int* maze, int m, int n)
{
    if (!maze || m <= 0 || n <= 0)  // sentry
        return;
    int* path = new int[m]; // path trace mem
    for (int j = 0; j < 3; ++j)
        Traverse(maze+j,0,j,m,n,path);
    delete [] path;
}

int main(){
    int maze[3][3] = {{11, 12, 13},{21, 22, 23},{31, 32, 33}};
    TraverseGrid(maze[0],3,3);
    return 0;
}

This function is more flexible, it accepts any 2D grids.

[Everlong]

Thanks this helped quite a bit. I improved/modified a few things.