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

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

Question

Is there a different way of storing row,col and path
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 = "";
            }

        }
    }

I wonder if you could somehow expand the Node class to include some information so that you don't need a queue. Perhaps you could add: Direction from which you entered the node (needs 2 bits, for 4 possible entry edges), Directions from which you have exited the node (needs 4 bits, 1 per edge) and any other info I haven't thought of. You'd need to keep the (x,y) location of your "current" node as well (this is not stored in any node, of course). Not really sure if this is a good idea, but perhaps worth thinking about. — Matthew Watson, Feb 16 '13 at 20:44
Reach `[n, n]` how? What directions can you take? You should better describe your problem. And do you want to count or print these paths? — IVlad, Feb 16 '13 at 21:16
I'm confused. Do you need all possible combinations on nxn (increasing by one row or column each time in the path) or is nxn a maze, meaning only some movements would be allowed? — גלעד ברקן, Feb 16 '13 at 21:32
In your first sentence you state that you want to know the number of paths. So you don't need to remember the paths. Is that correct? — Reinstate Monica, Feb 16 '13 at 21:36

IVlad · Answer 1 · 2013-02-16T22:02:53.863

3

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.

edited Feb 16 '13 at 22:02

answered Feb 16 '13 at 21:55

IVlad

43,099
13
111
179

nice !.. how do we keep track of the paths travelled ? – SheldonCooper Feb 16 '13 at 22:15
@SheldonCooper - if you want to print all paths, you will need to use backtracking (recursive or not). The number of paths grows exponentially, so it will quickly become unfeasible as `n` increases. – IVlad Feb 16 '13 at 22:23

score 1 · Accepted Answer · edited May 23 '17 at 12:18

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

score 0 · Answer 3 · answered Feb 25 '14 at 04:24

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);

Find number of ways in a maze non recursively

3 Answers3