I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are right and up.
Also, you can't move below the diagonal y=x. e.g if you're at (1,1) you can only move to (1,2), but not to (2,1), since it's below the y=x diagonal.
I wrote an algorithm that calculates the number of possible paths from (0,0) to any given (x,y), such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.
The algorithm I wrote is a bottom-up one, as follows:
JUMP(x, y) 1. M[x-1,y+1] ← 1 2. for i=0 to x+1 M[i,y+1] ← 0 3. for i=0 to y+1 M[x+1,i] ← 0 4. for j=0 to y-1 for i=j+1 to x M[i,j] ← 0 5. for j=y to 0 for i=j to 0 M[i,j] ← M[i+1,j] + M[i,j+1] 6. return M[i,j]
Please advise on this.