使用递归从左上方到右下方找到网格中的第一条路径

Question

我尝试使用递归从网格的左上角移动到右下角。然而，在每一个时间点，我只能向上、向下、向左或向右移动我所站的数字所给出的正方形数。

举个例子，如果你站在一个3上，我可以向左移动三个格子，向右移动三个格子，向上移动三个格子，或者向下移动三个格子。我不能离开棋盘。

我试图寻找一个起点，但我是空白的。有人可以帮忙吗？

        public int traverse(int[][] grid, int size, int x, int y){

            // base condition
            if(x == size-1 & y == size-1)
                return 0;

            // value of current square
            int square = grid[y][x];

            // move right
            if(x + square < size)
                return square + traverse(grid, size, x + square, y);

            // move down
            if(y + square < size)
                return square + traverse(grid, size, x, y + square);

            // move left
            if(x - square > -1)
                return square + traverse(grid, size, x - square, y);

            // move up
            if(y - square > -1)
                return square + traverse(grid, size, x, y - square);

            return 0;
        }

Answer 1

您需要任务的DFS，它还可以跟踪当前访问的路径。这是一个简单的Python实现，可以很容易地在其他语言中进行优化和实现。

def dfs(i, j, matrix, visited, path):
    # check if current point if out of bounds
    if i < 0 or i> len(matrix):
        return []
    if j < 0 or j> len(matrix[0]):
        return []
    
    # check if current point has been visited earlier
    if visited.get((i,j)):
        return visited[(i,j)]

    # add current point to path
    new_path = path + [(i,j)]

    # check if we've reached bottom right point
    if i==len(matrix)-1 and j == len(matrix[0])-1:
        return new_path
    
    # so that dfs doesn't get stuck in infinite recursion for cycles
    visited[(i,j)] = []

    value = matrix[i][j]
    possible_paths = [
        dfs(i+value,j,matrix,visited,new_path),
        dfs(i-value,j,matrix,visited,new_path),
        dfs(i,j+value,matrix,visited,new_path),
        dfs(i,j-value,matrix,visited,new_path)
    ]

    for option in possible_paths:
        if option:
            # we have found a path
            visited[(i,j)] = option
            return option
    
    #no path found
    return []