This is a Python program to count all paths in an m x n grid with holes using dynamic programming with memoization.
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 memoization. That is, the function is implemented recursively and as values are computed they are stored in a table to avoid recomputation.
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 memoization. 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)] 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))
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): 3, 4 Enter the coordinates of holes on each line (empty line to stop): Number of paths from (0, 0) to (4, 3): 35. Case 2: Enter m, n for the size of the m x n grid (m rows and n columns): 8, 9 Enter the coordinates of holes on each line (empty line to stop): 2, 5 3, 3 5, 8 Number of paths from (0, 0) to (9, 8): 12103. Case 3: Enter m, n for the size of the m x n grid (m rows and n columns): 10, 5 Enter the coordinates of holes on each line (empty line to stop): 2, 4 4, 4 Number of paths from (0, 0) to (5, 10): 1358.
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.
- Check Python Books
- Practice Programming MCQs
- Apply for Python Internship
- Check Information Technology Books
- Apply for Programming Internship