CODEWITHSUNDEEP
algorithmgraphdynamic-programmingbacktracking
Cereal_Killer
Cereal_Killer

Reputation: 324

count number of uniq paths in maze

I know the backtracking approach to count path [0,0] to [n,n] in matrix. but not able to solve it by dynamic programming. Is it even possible without backtracking ??

you can move only right or down

1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
`

number of path to reach from top left to bottom right is 4

Upvotes: 1

Views: 1198

Answers (3)

Eugene Yarmash
Eugene Yarmash

Reputation: 149726

Yes, you can use dynamic programming to solve this.

  • Given a M x N maze, initialize an array paths with the same dimensions. Let paths[i][j] be the number of possible paths from maze[0][0] to maze[i][j].
  • Initialize paths[0][0] to 1.
  • If maze[i][j] == 0, then paths[i][j] = 0 else paths[i][j] = paths[i-1][j] + paths[i][j-1].

Here's a Python implementation:

def number_of_paths(maze):
    paths = [[0 for col in range(len(maze[0]))] for row in range(len(maze))]
    paths[0][0] = 1

    for row in range(len(maze)):
        for col in range(len(maze[0])):
            if maze[row][col] == 0:
                paths[row][col] = 0
            else:
                if row != 0:
                    paths[row][col] += paths[row-1][col]
                if col != 0:
                    paths[row][col] += paths[row][col-1]
    return paths[-1][-1]

maze = [[1, 1, 1, 1],
        [1, 0, 1, 1],
        [1, 1, 0, 1],
        [1, 1, 1, 1]]

print(number_of_paths(maze))  # 4

Upvotes: 0

Amit Kumar Sharma
Amit Kumar Sharma

Reputation: 1

    static int numPath = 0;
    // Take one sol[][] of same size as original matrix just to see your paths.
    private static boolean MazeSolvingAllPaths(int [][] matrix, int x, int y, int[][] sol) {


        //Base case
        if(x == (sizeofMatrix -1) && y == (sizeofMatrix -1)) {
            sol[x][y] = 1;
            numPath++; // Path found so increase numPath here
            return true;
        }
        if(isSafeAllPaths(matrix, x, y) == true && matrix[x][y] == 1) {
            sol[x][y] = 1; // Mark this as solution path in solution matrix
            // Go right and down for (x, y)
            boolean var1 = MazeSolvingAllPaths(matrix, x, y+1, sol);
            boolean var2 = MazeSolvingAllPaths(matrix, x+1, y, sol);
            // If atleast one solution i found then return true
            if(var1 || var2) {                  
                return true;
            } else { // means both var1 and var2 are false
                sol[x][y] = 0;// unmark because i couldn't find path
                return false;
            }
        }
        return false;
    }

Upvotes: 0

Dave
Dave

Reputation: 9065

Yep. Say p(i,j) is the number of partial paths to i,j. If we're using zero-indexing then what you want is p(n-1,n-1). What you know is that p(0,0)=1, also p(i,j) is the sum of the value to the left if you can travel from p(i-1,j) to p(i,j), and the value above if you can travel from p(i,j-1) to p(i,j).

So you use all that to fill out a matrix. Pretty much that's what DP is: matrix-filling. Once you figure out how to fill out the matrix you're done.

Upvotes: 3

Related Questions