通过矩阵查找所有路径

Question

虽然我有一个矩阵如下，从左上角找到所有的路径，直到得到'0'。 'D'代表底部元素是trace的下一步。 “R”代表正确的元素。 “B”代表底部和右侧元素是可选的。 “C”代表右下角的元素。在

[['R' 'C' 'D' 'B' 'D' 'C' '0']
 ['C' 'B' 'C' 'B' 'D' 'D' '0']
 ['B' 'D' 'B' 'B' 'C' 'D' '0']
 ['R' 'C' 'B' 'D' 'B' 'C' '0']
 ['B' 'B' 'R' 'C' 'B' 'D' '0']
 ['R' 'C' 'B' 'R' 'R' 'C' '0']
 ['C' 'R' 'C' 'B' 'B' 'B' '0']
 ['0' '0' '0' '0' '0' '0' '0']]

在这种情况下，有两条路径满足要求，它们是

^{pr2}$

我尝试使用递归函数来查找这两条路径中的所有“C”， 因为在（2，3）B中有一个fork，所以函数只在joint之后完全返回其中一个路径。在

(5, 5)C(4, 3)C
(3, 5)C(2, 4)C(1, 2)C(0, 1)C

所以我如何修改我的代码来获得整个结果呢？在

def printC(matrix, i=0, j=0):
    if matrix[i][j] == '0':
        print()
        return None
    elif matrix[i][j] == 'B':
        printC(matrix, i+1, j)
        printC(matrix, i, j+1)
    elif matrix[i][j] == 'D':
        printC(matrix, i+1, j)
    elif matrix[i][j] == 'R':
        printC(matrix, i, j+1)
    elif matrix[i][j] == 'C':
        printC(matrix, i+1, j+1)
        print((i,j), end='')
        print(matrix[i][j], end='')

printC(matrix)
print()

谢谢

Answer 1

我想这可能更接近你想要的：

def printC(matrix, i=0, j=0, previous=None):
    if not previous:
        previous = []
    if matrix[i][j] == '0':
        print()
        return None
    elif matrix[i][j] == 'B':
        previous_branch = previous[:]
        printC(matrix, i+1, j, previous)
        print(''.join(reversed(previous_branch)), end='')
        printC(matrix, i, j+1, previous)
    elif matrix[i][j] == 'D':
        printC(matrix, i+1, j, previous)
    elif matrix[i][j] == 'R':
        printC(matrix, i, j+1, previous)
    elif matrix[i][j] == 'C':
        previous.append('{}{}'.format((i,j), matrix[i][j]))
        printC(matrix, i+1, j+1, previous)
        print((i,j), end='')
        print(matrix[i][j], end='')

诀窍是存储以前的命令，然后在遍历另一个分支时重新编译它们。之所以必须反转这些命令，是因为在递归中选择的回溯方法在路径被采用之后打印命令，这意味着最新的命令首先被打印，因为它首先被解析，等等。在

不幸的是，由于递归方法，代码有点复杂；在这种情况下，我实际上认为迭代方法更适合。在

编辑：这是一种迭代的方法，不过我必须指出，嵌套列表可能不是最好的树替代：

^{pr2}$

Answer 2

用于此问题的自然算法是backtracking：

• 继续，在所有选项中选择第一个选项
• 到达终点后，返回（回溯）并选择下一个选项；如果没有其他选项可用，则返回更远的位置
• 从初始元素回溯之后，您已经用尽了所有路径。在

你在两种情况下“达到了终点”：

• 点击0=>；将当前路由添加到结果中
• 你击中了一个已经在路由中的元素，也就是说，有一个循环。
  • 按照你的规则，这是不可能的：一步一步走下去，对吧，或者两者兼而有之。所以我们不需要担心这个。在

---

为了跟踪进度，我们需要：

• 当前坐标
  • 整数

• 当前路由，具有附加到结尾和从结尾弹出的能力（即a stack）。我们还需要存储最后的选择。在

  • Pythonlist支持此功能：

    route = []
    # go forward
    route.append((new_x,new_ym,choice))
    # backtrack
    route.pop()
    x,y,last_choice = route[-1]
    

• 找到的一系列路由，具有附加到末尾的能力

  • 同样，一个list：

    results=[]
    # add result
    results.append(tuple(step[:2] for step in route))    # don't need choices in result
    

整个程序将如下所示（在伪代码中）：

initialization
while True:
    if can_step_forward:
        make_step_with_the_next_choice
        if hit_0:
            add_result
    else:
        backtrack
        if backtracked_past_the_beginning:
            break

return result

利用所有这些，你现在能把解决方案组合起来吗？在