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