Python Program to Count all Paths in a Grid with Holes using Dynamic Programming with Memoization

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)]
    return count_paths_helper(m, n, holes, paths, n, m)
 
 
def count_paths_helper(m, n, holes, paths, x, y):
    """Return number of paths from (0, 0) to (x, y) 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.
 
    The function uses the table paths (implemented as a list of lists) where
    paths[a][b] will store the number of paths from (0, 0) to (a, b).
    """
    if paths[x][y] >= 0:
        return paths[x][y]
 
    if (x, y) in holes:
        q = 0
    elif x == 0 and y == 0:
        q = 1
    elif x == 0:
        q = count_paths_helper(m, n, holes, paths, x, y - 1)
    elif y == 0:
        q = count_paths_helper(m, n, holes, paths, x - 1, y)
    else:
        q = count_paths_helper(m, n, holes, paths, x - 1, y) \
            + count_paths_helper(m, n, holes, paths, x, y - 1)
 
    paths[x][y] = q
    return q
 
 
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))

Output

Enter m, n for the size of the m x n grid (m rows and n columns): 3, 4
Enter the coordinates of holes on each line (empty line to stop): 
 
Number of paths from (0, 0) to (4, 3): 35.