python-3.xtopdownbottom-up

How do you implement the bottom-up and top-down approach in this problem?


I am given a grid or n * n. I need to find how many routes I can take to get from grid[0][0] to grid[n - 1][n - 1]. However in the grid there will be the letter 'H' in some of the spaces. If there is an "H", I cannot cross that place. I can only go to the right of down. I need to use the top-down approach and the bottom-up approach but I don't know how to do that. Here is an example:

grid = [['.', '.', '.', '.'],
       ['.', '.', '.', 'H'],
       ['.', '.', 'H', '.'],
       ['.', '.', '.', '.']]

I need to go from the first element to the last element without going through the 'H's. The answer to this example is 4.


Solution

  • Here they have the solution https://www.geeksforgeeks.org/count-number-ways-reach-destination-maze/

    R = 4
    C = 4
    def countPaths(maze):
         
        if (maze[0][0] == -1):
            return 0
     
        for i in range(R):
            if (maze[i][0] == 0):
                maze[i][0] = 1
     
            else:
                break
     
        for i in range(1, C, 1):
            if (maze[0][i] == 0):
                maze[0][i] = 1
     
            else:
                break
    
        for i in range(1, R, 1):
            for j in range(1, C, 1):
                 
                if (maze[i][j] == -1):
                    continue
    
                if (maze[i - 1][j] > 0):
                    maze[i][j] = (maze[i][j] +
                                  maze[i - 1][j])
     
    
                if (maze[i][j - 1] > 0):
                    maze[i][j] = (maze[i][j] +
                                  maze[i][j - 1])
     
        if (maze[R - 1][C - 1] > 0):
            return maze[R - 1][C - 1]
        else:
            return 0
     
    
    if __name__ == '__main__':
        maze = [[0, 0, 0, 0],
                [0, -1, 0, 0],
                [-1, 0, 0, 0],
                [0, 0, 0, 0 ]]
        print(countPaths(maze))