如何在这个问题中实现自底向上和自顶向下的方法?

Question

给定一个网格或n * n，我需要找出从网格[0][0]到网格[n - 1][n - 1]可以走多少条路。然而，在网格中，在一些空格中会有字母"H"。如果有一个"h"字，我不能穿过那个地方。我只能向右移动。我需要使用自上而下的方法和自下而上的方法但我不知道怎么做。下面是一个例子:

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

我需要从第一个元素到最后一个元素，而不需要经过"H"。这个例子的答案是4。

Answer 1

他们有了解决方案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))