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