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

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 []

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

Find the first path in a grid from top left to bottom right using recursion

java

algorithm

recursion