Printing all Paths in a binary matrix

Question

A 'path' in a binary matrix of size N is an ordered collection of cells starting from (0,0) and ending at (N,N) such that the entry of each cell in the path is 1.

e.g-> Matrix:

has two paths:
(0,0)->(0,1)->(1,1)->(2,2)->(3,3) and
(0,0)->(1,0)->(1,1)->(2,2)->(3,3)

What is the best approach to print all possible paths? Currently, I can only think of the brute force solution where I keep following the lowermost '1's and making them zero one by one.

I assume possible directtions are left and down again - otherwise you have a cycle and there are infinite number of paths. — amit, Nov 07 '12 at 08:51
There's not really enough detail in your proposed solution, czardoz. "Brute Force" means going through all possible paths, but you haven't really how your proopsed solution is brute force. — Josh Greifer, Nov 07 '12 at 08:51
What I am doing right now is, I start at (0,0) and reach some (i,j) [both i and j may be zero] where I find the first branch (meaning two of the entries among (i+1,j),(i+1,j+1) and (i,j+1) are '1') Then I select one, and make that entry zero so it's not used again. I repeat the process until no path is left — czardoz, Nov 07 '12 at 08:57

score 3 · Answer 1 · answered Nov 07 '12 at 08:58

Model your problem as a graph G=(V,E) where:
V = { all nodes marked as 1 } and
E = { (u,v) | u,v are in V and u,v are "neighbors" in the matrix }

The simplest way to find ALL paths is using a DFS without maintaining a visited set - and iteratively doing it until you exhausted all possible paths.

Note that if the graph has cycles (and you actually want all simple paths, because there could be infinite number of paths in a graph with cycles) - then you are going to need to maintain a "special" visited set per path - this set will hold all nodes in the current explored path, and a vertex will be deleted from it once you "go back" from the recursive call in DFS.

Note that the number of paths is exponential - and you want to print them all - so the run time cannot be sub-exponential to this problem.

+1, cycles should not be a concern, DFS would only go to (In+1 >= In && Jn+1 >= Jn && !(In==In+1 && Jn==Jn+1)) nodes — bobah, Nov 07 '12 at 09:06
@bobah: cycles are not concern only if you assume these are indeed all the possible directions, if you could up and left as well - there could be a cycle. I added an indication for it for completeness of the answer. — amit, Nov 07 '12 at 09:22

score 1 · Answer 2 · edited May 23 '17 at 12:29

Your question is not very clear.I assume that possible directions are right one step (eg: (1,1) -> (1,2) ), down one step (eg:(1,1,) -> (2,1)) or both right and down one step(eg: (1,1) -> (2,2)). Otherwise, just as discussed by amit, there could be infinite number of paths.

And the case in your question, there should be three possible paths. Just as nav_jan mentioned, (0,0)->(1,1)->(2,2)->(3,3) is also a possible path.

I designed a recursive method, it is quite easy to understand. Start from (0,0) point and try to move in three directions. If current point is 1, keep moving, otherwise return. Once reaching the (n-1,n-1) point, a valid path is found.

The code is in written Java.

public static List<String> getMatrixPaths(int[][] matrix){
    List<String> pathList = new ArrayList<String>();
    if(matrix != null && matrix.length > 0){
        getMatrixPaths(matrix, 0,0, "", pathList);
    }
    return pathList;
}
public static void getMatrixPaths(int[][] matrix, int i, int j, String path, List<String> pathList){
    int n = matrix.length - 1;
    if(i > n || j > n){
        return;
    }else if( matrix[i][j] == 1){//only 1 is valid
        path += String.format(" (%d,%d)", i , j);
        if( i ==n && j == n){ // reach (n,n) point
            pathList.add(path);
        }else {
            getMatrixPaths(matrix, i +1, j , path, pathList);
            getMatrixPaths(matrix, i , j +1, path, pathList);
            getMatrixPaths(matrix, i + 1 , j +1, path, pathList);
        }
    }
}

Use the matrix in question for test, my result is [ (0,0) (1,0) (1,1) (2,2) (3,3), (0,0) (0,1) (1,1) (2,2) (3,3), (0,0) (1,1) (2,2) (3,3)] .

you may refer to this question: Algorithm for finding all paths in a NxN grid . I think they are quite similar.

Printing all Paths in a binary matrix

2 Answers2