当前位置: 首页 > 知识库问答 >
问题:

使用规则从网格中查找路径

郗浩言
2023-03-14

我正在学习bfs/dfs,并试图解决这个问题。有一个n×n的网格。找到在网格中从源单元格移动到目标单元格所需的路径(不一定是最短路径),并返回这些单元格之间的路径。每个网格单元格都有一个值。我们可以一次向四个方向移动一步:上、下、左、右。我们只能移动到具有相等或较小值的相邻单元格。如果没有移动可能到达目标,则返回无。目标在右下角,起点在左上角

input:
grid1 = [
[4,3,5],
[2,3,3],
[2,2,1]
]

output:
[4,3,3,2,1] or [4,2,2,2,1] or [4,3,3,2,2,2,1] or [4,3,3,3,1]

下面是我的解决方案,但似乎结果与输出结果混合在一起。任何人都可以帮助我??

import collections
def findPath(grid):
    n = len(grid)
    seen = set()
    dirs = [(-1,0), (1,0), (0,1), (0,-1)]
    res = []
    queue = collections.deque()
    queue.append((0,0))
    res.append(grid[0][0])
    while queue:
        i,j = queue.popleft()
        for x,y in dirs:
            new_i = x + i
            new_j = y + j
            if new_i<0 or new_i>=n or new_j<0 or new_j>=n or grid[new_i][new_j] > grid[i][j]:
                continue
            if (new_i, new_j) in seen:
                continue
            # print((new_i,new_j))
            # print(grid[new_i][new_j])
            res.append(grid[new_i][new_j])
            if new_i==n-1 and new_j == n-1:
                return res
            seen.add((new_i, new_j))
            queue.append((new_i, new_j))
    return None   
    

共有1个答案

柯良骏
2023-03-14

因为我认为这是一个问题,其中递归是最简单的解决方案,我做了一个示例实现:

函数查找所有路径:

def find_paths_recursive(grid, current_path=[(0,0)], solutions=[]):
    n = len(grid)
    dirs = [(-1,0), (1,0), (0,1), (0,-1)]
    
    last_cell = current_path[-1]
    
    for x,y in dirs:
        new_i = last_cell[0] + x
        new_j = last_cell[1] + y
        
        # Check if new cell is in grid
        if new_i<0 or new_i>=n or new_j<0 or new_j>=n:
            continue
            
        # Check if new cell has bigger value than last
        if grid[new_i][new_j] > grid[last_cell[0]][last_cell[1]]:
            continue
        
        # Check if new cell is already in path
        if (new_i, new_j) in current_path:
            continue

        # Add cell to current path
        current_path_copy = current_path.copy()
        current_path_copy.append((new_i, new_j))

        if new_i==n-1 and new_j == n-1:
            solutions.append(current_path_copy)
        
        # Create new current_path array for every direction
        find_paths_recursive(grid, current_path_copy, solutions)
        
    return solutions

函数获取路径的值:

def compute_cell_values(grid1, solutions):
    path_values = []

    for solution in solutions:
        solution_values = []
        for cell in solution:
            solution_values.append(grid1[cell[0]][cell[1]])
        path_values.append(solution_values)
    return path_values

例子:

grid1 = [
[4,3,5],
[2,3,3],
[2,2,1]
]


solutions = find_paths_recursive(grid1)
path_values = compute_cell_values(grid1, solutions)

print('Solutions:')
print(solutions)
print('Values:')
print(path_values)

示例输出:

Solutions:
[[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)], [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)], [(0, 0), (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2)]]
Values:
[[4, 2, 2, 2, 1], [4, 3, 3, 2, 1], [4, 3, 3, 3, 1], [4, 3, 3, 2, 2, 2, 1]]

注意:描述路径中单元格的值不是坐标,而是数组索引,这一点很重要。这意味着单元格的第一个值是网格中的y值。

编辑:由于递归并不总是(或基本上不是)最好的解决方案,而且你对队列有一个很好的想法,所以我提出了另一个解决方案。与您的解决方案不同的是,队列存储了我们探索的路径。它只返回一条路径(如果存在),但它是最短的路径。

def find_path(grid):
    n = len(grid)
    dirs = [(-1,0), (1,0), (0,1), (0,-1)]
    queue = collections.deque()
    queue.append([(0,0)])
    
    while queue:
        current_path = queue.popleft()
        last_cell_i = current_path[-1][0]
        last_cell_j = current_path[-1][1]
        
        for x,y in dirs:
            new_i = x + last_cell_i
            new_j = y + last_cell_j
            
            # Check if new cell is in grid
            if new_i<0 or new_i>=n or new_j<0 or new_j>=n:
                continue
                
            # Check if new cell has bigger value than last
            if  grid[new_i][new_j] > grid[last_cell_i][last_cell_j]:
                continue
            
            # Check if new cell is already in path
            if (new_i, new_j) in current_path:
                continue
            
            # Add cell to current path
            current_path_copy = current_path.copy()
            current_path_copy.append((new_i, new_j))
        
            if new_i==n-1 and new_j == n-1:
                return current_path_copy
            
            queue.append(current_path_copy)
    return None 
 类似资料:
  • 因为我用谷歌表单收集数据。数据源不是我想要的,所以我需要创建一个选项卡并转换数据。 下面是Google表单的一个示例(从Google表单导出) 我将名称网格转换为数组(下面的第一列)。我的问题是如何找到相应的领导者(下面的第二列)? 非常感谢你

  • 这里的单元格1代表死单元格。有什么方法可以通过使用DFS或动态编程E.T.C来降低时间复杂性吗?

  • 我的想法: 回溯解决方案,我们通过所有解决方案的树和打印,一旦我们达到目标单元格。我实现了这一点,但我不确定它是否正确或有意义,或者它是否是正确的方法。我在这里发布了代码,如果有人能解释它的错误,我将非常感谢。 递归解决方案,我从起始单元格开始,并从每个相邻单元格递归地找到目标单元格的路径,基本情况是击中目标单元格。 5)有没有更简单的方法来做到这一点? 下面是我的代码,它打印N=4的正确路径数。

  • 我正在尝试了解如何使用动态编程解决在网格中查找所有唯一路径的问题: 机器人位于m x n网格的左上角(下图中标记为“开始”)。机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角(下图中标记为“Finish”)。有多少种可能的独特路径? 我正在看这篇文章,我想知道为什么在下面的解决方案中,矩阵被初始化为和,以及为什么在的函数签名中,最后一个参数被初始化为 然后在作者自下而上的解决方案

  • 我设置了一个作业来在Reports\pep8.log中查找pep8.log文件 但当我运行该作业时,我发现违规插件查找报告的路径没有意义: 生成的xml文件:C:\jenkins\jobs\python-template-2\workspace\reports\pep8.log=============================================================

  • 在BeX5中,功能树上会出现类似$UI/…/…/xx.a的url, 其中“.a”是一种特殊的url,“.a”通过以下规则,最终定位到具体的.w文件: 1. 如果登录的门户是5.3之前的门户 如果客户端是手机: 查找.w文件的顺序是 第一步:查找/mobileUI下相应的.w文件; 第二步:查找/UI2下相应的.m.w文件; 第三步:查找/UI2下相应的.w文件; 如果客户端是PC: 查找.w文件的