CODEWITHSUNDEEP
algorithmmathmatrixgraph
Abhinesh
Abhinesh

Reputation: 123

Count all path in a binary matrix

A matrix of NxN has either 0 and 1.
0 means he can pass through this cell and 1 means it is blocked.
he can move in all four direction{ if his current location is (X,Y), he can move to either (X+1,Y), (X−1,Y), (X,Y+1), (X,Y−1) }.
If the first cell (1,1) and the last cell(N,N) contain '1' ,then he can't break out of the matrix.

he wants to know the total number of unique possible paths which he can take to escape the prison.Initially Alfie is in cell (1,1) while the exit of the cell (N,N).

Example :
Input
4
0 1 1 0
0 0 1 0
0 0 0 0
0 1 1 0
Output:
2

Input :
4
0 0 0 1
0 0 0 0
1 1 1 0
1 0 0 0
Output:
4

Input :
4
0 1 1 0
0 0 1 1
0 0 0 0
0 1 0 0
Output:
4

I know how to solve when it moves only two direction down and right.
But how to approach problem like this when it moves in four direction..?

Upvotes: 0

Views: 1017

Answers (1)

Rory Daulton
Rory Daulton

Reputation: 22564

The easy part about the related problem "when it moves only two direction down and right" is that the path cannot double back on itself. If you allow all four directions, as in your current problem, you need the restriction that Alfie may not visit a cell more than once. Without that restriction, Alfie could oscillate back and forth between two cells, or keep going in a circle, causing infinitely many paths. So we add that restriction: a cell may be visited at most once.

We need to enforce that restriction. An easy way to do this is to make a second NxN matrix, but this one using only Boolean values. We can call it visited and define it by visited[X][Y] is True if and only if Alfie has visited that cell during the current path; otherwise it is False. (Another way is to mark a visited cell with a 2 to distinguish it from a wall or non-visited cell--I thought of this later but it would use less memory.)

There are multiple algorithms that can now solve the problem. Perhaps the easiest way is to have an outer routine that sets things up and call an inner recursive routine to add up the paths. Here is some Python-like pseudocode, ignoring some efficiencies for the sake of clarity. Note that matrices in Python are zero-based, so the two corners of the prison are at (0,0) and (N-1, N-1).

def count_paths(N, prison):
    """Return the total number of unique possible paths which Alfie can
    take to escape the prison."""

    def count_paths_recurse(X, Y, prison, visited):
        """Return the number of paths starting from cell (X, Y) where
        pathcount visited[] marks the cells not to visit."""
        if X == N-1 and Y == N-1:  # reached the exit cell
            return 1
        visited[X][Y] = True
        pathcount = 0
        for direction in (right, left, down, up):
            Xnew, Ynew = neighoring cell coordinates in that direction
            if Xnew and Ynew are inside the prison
                    and prison[Xnew][Ynew] == 0
                    and not visited[Xnew][Ynew]:
                pathcount += count_paths_recurse(Xnew, Ynew, prison, visited)
        visited[X][Y] = False
        return pathcount

    if prison is not an NxN matrix containing only 0s and 1s:
        raise an error
    create visited as an NxN matrix containing only False
    if prison[0][0] != 0 or prison[N-1][N-1] != 0:
        return 0
    return count_paths_recurse(0, 0, prison, visited)

Since the directions from each cell are in a consistent order (right, left, down, up in this code), each path will be unique. I have build a full Python program from this algorithm, and it works, giving the desired answers in all three examples.

Upvotes: 2

Related Questions