Find number of ways in a maze non recursively

Question

Given a matrix[n,n] I want to find out how many ways we can reach from [0,0] to [n,n] non recursively.

My approach is to

1. Create a stuct Node to store row, col and path travelled so far
2. Add node to a Queue
3. Iterate thru queue till not empty . Increment row, increment col. Add to Queue
4. Print the path if row=n, col=n

Question

1. Is there a different way of storing row,col and path
2. If n is very large, storing nodes in Queue can be a problem. How can we avoid this?

Please not I am not looking for recursive solution. I see such questions in many interview forums and so want to know if this would be the right approach.

Below is the structure of Node and the function

 struct Node
    {
        public int row;
        public int col;
        public string path;

        public Node(int r, int c, string p)
        {
            this.row = r;
            this.col = c;
            this.path = p;
        }
    }




 public static void NextMoveNonRecursive(int max)
    {

        int rowPos;
        int colPos;
        string prevPath = "";
        Node next;

        while (qu.Count > 0)
        {
            Node current = qu.Dequeue();
            rowPos = current.row;
            colPos = current.col;
            prevPath = current.path;

            if (rowPos + 1 == max && colPos + 1 == max)
            {
                Console.WriteLine("Path = ..." + prevPath);
                TotalPathCounter++;
            }

            if (rowPos + 1 < max)
            {
                if (prevPath == "")
                    prevPath = current.path;

                prevPath = prevPath + ">" + (rowPos + 1) + "" + (colPos);
                next = new Node(rowPos + 1, colPos, prevPath);
                qu.Enqueue(next);
                prevPath = "";
            }

            if (colPos + 1 < max)
            {

                if (prevPath == "")
                    prevPath = current.path;

                prevPath = prevPath + ">" + (rowPos) + "" + (colPos+1);
                next = new Node(rowPos, colPos+1, prevPath);
                qu.Enqueue(next);
                prevPath = "";
            }

        }
    }

Answer 1

Given a matrix [n,n], how many ways we can reach from [0,0] to [n,n] by increasing either a col or a row?

(n*2-2) choose (n*2-2)/2

If you can only go down or right (i.e., increase row or col), it seems like a binary proposition -- we can think of 'down' or 'right' as '0' or '1'.

In an nxn matrix, every path following the down/right condition will be n*2-2 in length (for example, in a 3x3 square, paths are always length 4; in a 4x4 square, length 6).

The number of total combinations for 0's and 1's in binary numbers of x digits is 2^x. In this case, our 'x' is n*2-2, but we cannot use all the combinations since the number of 'down's or 'right's cannot exceed n-1. It seems we need all binary combinations that have an equal number of 0's and 1's. And the solution is ... tada:

(n*2-2) choose (n*2-2)/2

In Haskell, you could write the following non-recursive function to list the paths:

import Data.List
mazeWays n = nub $ permutations $ concat $ replicate ((n*2-2) `div` 2) "DR"

if you want the number of paths, then:

length $ mazeWays n

Answer 2

Let dp[i, j] be the number of paths from [0, 0] to [i, j].

We have:

dp[0, i] = dp[i, 0] = 1 for all i = 0 to n
dp[i, j] = dp[i - 1, j] +     come down from all paths to [i - 1, j]
           dp[i, j - 1] +     come down from all paths to [i, j - 1]         
           dp[i - 1, j - 1]   come down from all paths to [i - 1, j - 1] 
           for i, j > 0

Remove dp[i - 1, j - 1] from the above sum if you cannot increase both the row and the column.

dp[n, n] will have your answer.

Answer 3

Javascript solutions with sample

var arr = [
    [1, 1, 1, 0, 0, 1, 0],
    [1, 0, 1, 1, 1, 1, 0],
    [1, 0, 1, 0, 1, 0, 0],
    [1, 1, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1]
];

function sols2(arr){
    var h = arr.length,
            w = arr[0].length,
            i, j, current, left, top;

    for(i = 0; i < h; i++){
        for(j = 0; j < w; j++){
            current = arr[i][j];
            top = i === 0 ? 0.5 : arr[i - 1][j];
            left = j === 0 ? 0.5 : arr[i][j-1];

            if(left === 0 && top === 0){
                arr[i][j] = 0;
            } else if(current > 0 && (left > 0 || top > 0)){
                arr[i][j] = (left + top) | 0;
            } else {
                console.log('a6');
                arr[i][j] = 0;
            }       
        }
    }
    return arr[h-1][w-1];
}

sols2(arr);