python - 网格中的图形深度优先搜索 (DFS)

Question

问题

有 n x n 网格，您必须从第 0 行第 0 列（左上角）开始我想知道探索网格所有隔间的路线数，并且不要通过已经搜索过的隔间。示例：n = 2 → 2 条路径

def dfs(size, cur_pos, route : list): 
    # size : size of grid, cur_pos : (current_row, current_column). each_row/col starts at 0
    # route : list consists of positions so far. ex) [(0,0),(1,0),(1,1)]

    route.append(cur_pos)
    # append current position at route list first

    # escape condition
    if len(route) == pow(size, 2): # if length of route is same as the size of the grid
        result_list.append(route) # add 1 to the number of path
        return

    to_move = [(1,0),(-1,0),(0,1),(0,-1)] # amount to move. down/up/right/left

    for i in range(4):
        next_pos = (cur_pos[0] + to_move[i][0], cur_pos[1] + to_move[i][1])
        # set next position

        if 0 <= next_pos[0] < size and 0 <= next_pos[1] < size: # if next position is still in the grid
            if next_pos not in route: # if next position is not already searched
                dfs(size, next_pos, route) # search recursively

result_list = [] # save each complete routes

input_size = int(input())
dfs(input_size, (0,0), [])

print(len(result_list)) # always print 1....

这段代码总是打印 1...
我认为route每次搜索完成时变量似乎都没有被清除，但我不知道如何解决这个问题。有谁知道如何让它做到这一点？

标签： pythongraphgrid