动态规划 - 走出迷宫的方法数（有障碍）

Question

我正在尝试使用动态编程进行编码，这是一个 num_of_paths 函数来计算走出迷宫的方法数。进入的迷宫是一个包含n个元组的元组，每个元组有m个值。元组中的值为 0 或 1，0 代表该单元格中的炸弹。这是伪代码：

初始化一个空table（字典），获取行数n和列数m.
填写第一行。对于范围 m 中的 j:

2.1。如果 maze[0][j] 是安全的，请将 table[(0, j)] 设置为 1，因为只有一种方法可以到达那里。

2.2。如果 maze[0][j] 有炸弹，设置 table[(0, k)] 其中 k >= j 为 0。由于一路上有一个单元格被破坏，因此无法到达所有后续单元格（在第一行）。
填写第一列。对于范围 n:
中的 i
3.1 如果 maze[i][0] 是安全的，将 table[(i, 0)] 设置为 1，因为只有一种方法可以到达那里。

3.2 如果maze[i][0]有炸弹，则将table[(i, 0)]及其下的所有单元格设为0，同row.
主要DP程序-填写table的其余部分。如果 maze[i][j] 有炸弹，设置 table[(i, j)] = 0。否则，table[(i, j)] = table[(i - 1, j)] + table[(i, j - 1)].
Return table[(n - 1, m - 1)].

def num_of_paths(maze):
    # Step 1
    table = {}
    n = len(maze)
    m = len(maze[0])
    # Step 2
    for j in range(m):
        if maze [0][j] == 1: #Safe
            table[(0, j)] = 1
        else: #Bomb
            for k in range(j,):
                table[(0, k)] = 0
    for i in range(n): #Step 3
        if maze[i][0] == 1: #Safe
            table[(i,0)] = 1
        else: #Bomb
            table[(i,0)] = 0
    for j in range(1,m): #Step 4
        for i in range(1,n):
            if maze[i][j] == 0: #Bomb
                table[(i,j)] = 0
            else:
                table[(i,j)] = table[(i - 1, j)] + table[(i, j - 1)]
    return table[(n-1,m-1)] #Step 5

maze  = ((1, 1, 1, 1, 1, 1, 1, 1, 0, 1),
         (1, 0, 0, 1, 1, 1, 0, 0, 1, 1),
         (0, 1, 1, 1, 0, 0, 1, 1, 1, 0),
         (1, 1, 0, 1, 1, 1, 1, 0, 1, 1),
         (0, 1, 0, 1, 0, 0, 1, 0, 1, 0),
         (1, 0, 1, 1, 1, 1, 0, 1, 1, 1),
         (1, 1, 0, 1, 0, 1, 0, 0, 1, 1),
         (0, 1, 1, 1, 1, 1, 1, 1, 1, 0),
         (1, 0, 1, 0, 0, 1, 1, 0, 1, 1),
         (1, 0, 1, 1, 1, 0, 1, 0, 1, 0),
         (1, 1, 0, 1, 0, 1, 0, 1, 1, 1))

我得到了倒数第二行的 KeyError:(0,8)。我怀疑这是因为密钥不在我的字典中（？）任何人有解决此错误的建议，或编码的替代方法？

Answer 1

   def countPaths(maze):
     
    # If the initial cell is blocked,
    # there is no way of moving anywhere
    if (maze[0][0] == -1):
        return 0
 
    # Initializing the leftmost column
    for i in range(R):
        if (maze[i][0] == 0):
            maze[i][0] = 1
 
        # If we encounter a blocked cell in
        # leftmost row, there is no way of
        # visiting any cell directly below it.
        else:
            break
 
    # Similarly initialize the topmost row
    for i in range(1, C, 1):
        if (maze[0][i] == 0):
            maze[0][i] = 1
 
        # If we encounter a blocked cell in
        # bottommost row, there is no way of
        # visiting any cell directly below it.
        else:
            break
 
    # The only difference is that if a cell is -1,
    # simply ignore it else recursively compute
    # count value maze[i][j]
    for i in range(1, R, 1):
        for j in range(1, C, 1):
             
            # If blockage is found, ignore this cell
            if (maze[i][j] == -1):
                continue
 
            # If we can reach maze[i][j] from
            # maze[i-1][j] then increment count.
            if (maze[i - 1][j] > 0):
                maze[i][j] = (maze[i][j] +
                              maze[i - 1][j])
 
            # If we can reach maze[i][j] from
            # maze[i][j-1] then increment count.
            if (maze[i][j - 1] > 0):
                maze[i][j] = (maze[i][j] +
                              maze[i][j - 1])
 
    # If the final cell is blocked,
    # output 0, otherwise the answer
    if (maze[R - 1][C - 1] > 0):
        return maze[R - 1][C - 1]
    else:
        return 0

您可以访问 Geeksforgeeks 以获得更多解释： Click here

Answer 2

def num_of_paths(maze):
    # Step 1
    table = {}
    n = len(maze)
    m = len(maze[0])
    # Step 2
    for j in range(m):
        if maze [0][j] == 1: #Safe
            table[(0, j)] = 1
        else: #Bomb
            for k in range(j,m):
                table[(0, k)] = 0
            break
    for i in range(n): #Step 3
        if maze[i][0] == 1: #Safe
            table[(i,0)] = 1
        else: #Bomb
            for k in range(i,n):
                table[(k,0)] = 0
            break
    for j in range(1,m): #Step 4
        for i in range(1,n):
            if maze[i][j] == 0: #Bomb
                table[(i,j)] = 0
            else:
                table[(i,j)] = table[(i - 1, j)] + table[(i, j - 1)]
    return table[(n-1,m-1)] #Step 5

设法调试，结果发现我的else案例在2个for循环下有一些错误。

必须在 row/column
不得不跳出外层 for 循环

感谢所有帮助过的人！

动态规划 - 走出迷宫的方法数（有障碍）

Dynamic Programming - Number of ways to get out of a maze (with obstacles)

python

dynamic-programming