为什么递归不继续？

Question

我有两个清单。首先列出的是一个迷宫。它以“ O”开头，必须以“ X”结尾。

maze_list=[[0, 1, 1, 0, 0, 0],
          [0, 0, 1, 0, 1, 'O'],
          [0, 0, 1, 0, 1, 0],
          [0, 1, 1, 1, 1, 0],
          ['X', 1, 0, 1, 0, 0],
          [0, 1, 0, 1, 1, 1]]

path_list=[[0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0]]

此部分正在寻找开始位置。

column_size=len(maze_list)                  
row_size=len(maze_list[0])

def find_SF_position(X):
    liste=[]
    for i in range(column_size):
        for j in range(column_size):
            if maze_list[i][j]==X:
                liste.append(i)
                liste.append(j)
    return liste

s_p=find_SF_position('O')     #[1,5]
f_p=find_SF_position('X')     #[4,0]

这是主要算法。 x是水平位置。 y为垂直位置

def solve_maze(maze,road,x,y):
    global column_size
    global row_size
    road[y][x]=1
    print(y,x)
    #left
    if x>0 and maze[y][x-1]==1 and road[y][x-1]==0:
        return solve_maze(maze,road,x-1,y)
    #up
    if y>0 and maze[y-1][x]==1 and road[y][x-1]==0:
        return solve_maze(maze,road,x,y-1)
    #right
    if x>row_size and maze[y][x+1]==1 and road[y][x-1]==0:
        return solve_maze(maze,road,x+1,y)
    #down
    if y>column_size and maze[y+1][x]==1 and road[y][x-1]==0:
        return solve_maze(maze,road,x,y+1)
    if maze[x][y]=='X':
        return path_list
solve_maze(maze_list,path_list,s_p[1],s_p[0])

print(path_list)

我不明白为什么它不起作用。它以'O'（maze_list [1,5]）开始，它填充maze_list [1,4]然后停止。最后，path_list必须是这样的

path_list=[[0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 1, 1],
          [0, 0, 0, 0, 1, 0],
          [0, 1, 1, 1, 1, 0],
          [1, 1, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0]]

Answer 1

您的代码中有一些问题：

1. 首先，您的right和down条件相反：x绝不能大于row_size。您要检查的是x不在右边界上，表示：x < row_size - 1。 down情况

的逻辑相同

2. 好像您那里有一个复制粘贴问题：例如up的road条件应为：road[y-1][x]==0。其他所有情况也采用相同的逻辑。

3. 您寻找终点的条件有一个有问题的逻辑：您检查当前单元格是否为'X'，但是只有在下一个单元格中有1时才执行每个步骤，因此您将如何获得'X'？例如，修复上述错误后，我得到的输出是：

   [0, 0, 0, 0, 0, 0]
   [0, 0, 0, 0, 1, 1]
   [0, 0, 0, 0, 1, 0]
   [0, 1, 1, 1, 1, 0]
   [0, 1, 0, 0, 0, 0]
   [0, 1, 0, 0, 0, 0]
   

   您可以看到，由于在'X'处采用了[[down的条件，并且达到了死胡同，所以错过了(4, 1)

4. 最后，如果您走到尽头，会发生什么？您的算法始终在满足条件的情况下迈出第一步，但是遇到交集时会发生什么？您需要检查所有可能的路径。这就是递归的重点。您现在的操作方式并不会增加循环。