Python Program to Count all Paths in a Grid with Holes using Dynamic Programming with Bottom-Up Approach

This is a Python program to count all paths in an m x n grid with holes using dynamic programming with bottom-up approach.

We are given an m x n grid, i.e. a grid with m rows and n columns. We are also given a list of holes that the grid has. Each hole is a coordinate through which a path cannot pass. In addition, we are only allowed to move up or right. We want to find the number of paths from (0, 0) to (n, m).

1. The algorithm works by maintaining a table paths where paths[x][y] stores the number of paths from (0, 0) to (x, y).
2. paths will then satisfy the recurrence paths[x][y] = paths[x – 1][y] + paths[x][y – 1] if x, y > 0.
3. We also have paths[x][0] = paths[x – 1][0] for x > 0 and paths[0][y] = paths[0][y – 1] for y > 0 and paths[0][0] = 1
4. The above is true unless (x, y) is a hole in which case paths[x][y] = 0.
5. This is implemented using bottom-up approach. That is the function first computes paths[x][y] for the base cases as specified above. Then the function computes paths[x][y] in an order such that when paths[x][y] is to be computed, the values that are needed to compute it have already been found in a previous step.

Here is the source code of a Python program to count all paths in an m x n grid with holes using dynamic programming with bottom-up approach. The program output is shown below.

def count_paths(m, n, holes):
    """Return number of paths from (0, 0) to (m, n) in an m x n grid.
 
    holes is a list of tuples (x, y) where each tuple is a coordinate which is
    blocked for a path.
    """
    paths = [[-1]*(m + 1) for _ in range(n + 1)]
 
    if (0, 0) in holes:
        paths[0][0] = 0
    else:
        paths[0][0] = 1
 
    for x in range(1, n + 1):
        if (x, 0) in holes:
            paths[x][0] = 0
        else:
            paths[x][0] = paths[x - 1][0]
 
    for y in range(1, m + 1):
        if (0, y) in holes:
            paths[0][y] = 0
        else:
            paths[0][y] = paths[0][y - 1]
 
    for x in range(1, n + 1):
        for y in range(1, m + 1):
            if (x, y) in holes:
                paths[x][y] = 0
            else:
                paths[x][y] = paths[x - 1][y] + paths[x][y - 1]
 
    return paths[n][m]
 
 
m, n = input('Enter m, n for the size of the m x n grid (m rows and n columns): ').split(',')
m = int(m)
n = int(n)
print('Enter the coordinates of holes on each line (empty line to stop): ')
holes = []
while True:
    hole = input('')
    if not hole.strip():
        break
    hole = hole.split(',')
    hole = (int(hole[0]), int(hole[1]))
    holes.append(hole)
 
count = count_paths(m, n, holes)
print('Number of paths from (0, 0) to ({}, {}): {}.'.format(n, m, count))

1. The user is prompted to enter the dimensions of the m x n grid.
2. Then the user is asked to enter the coordinates of the holes on the grid.
3. The function count_paths is called to find the number of paths from (0, 0) to (n, m).
4. This is then displayed.

Case 1:
Enter m, n for the size of the m x n grid (m rows and n columns): 6, 10
Enter the coordinates of holes on each line (empty line to stop): 
5, 5
0, 1
 
Number of paths from (0, 0) to (10, 6): 4249.
 
Case 2:
Enter m, n for the size of the m x n grid (m rows and n columns): 10, 8
Enter the coordinates of holes on each line (empty line to stop): 
 
Number of paths from (0, 0) to (8, 10): 43758.
 
Case 3:
Enter m, n for the size of the m x n grid (m rows and n columns): 4, 4
Enter the coordinates of holes on each line (empty line to stop): 
1, 1
2, 2
 
Number of paths from (0, 0) to (4, 4): 18.

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.