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.

CodePudding user response：

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))