时间戳

首页 > 解决方案 > 在有障碍物的迷宫中查找路径的数量

python - 在有障碍物的迷宫中查找路径的数量

问题描述

我一直在研究这个leetcode 问题，它本质上是在给定一些obstacleGrid矩阵的情况下找到迷宫中有效路径的数量。如果obstacleGrid[i][j] == 1，那么我们在 (i,j) 处有障碍物，否则我们有零，这是一个有效点。我们只能以从左上到右下为目标上下左右移动。

我写了下面的代码：

def uniquePathsWithObstacles(self, obstacleGrid):
    # obstruction at the start
    if (obstacleGrid[0][0] == 1): return 0
    # obstruction at the end
    if (obstacleGrid[-1][-1] == 1): return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    memo = [[0] * n] * m
    # starting move
    memo[0][0] = 1
    # now check the first row
    for j in range(1, n):
        memo[0][j] = 1 if (obstacleGrid[0][j] == 0 and memo[0][j-1] != 0) else 0
    # now check the first column
    for i in range(1, m):
        memo[i][0] = 1 if (obstacleGrid[i][0] == 0 and memo[i-1][0] != 0) else 0
    # now check everything else
    for i in range(1, m):
        for j in range(1, n):
            if (obstacleGrid[i][j] == 1): memo[i][j] = 0
            else: memo[i][j] = memo[i-1][j] + memo[i][j-1]
    return memo[-1][-1]

我采用了明显的 DP 方法，我知道这个想法可行，但代码有问题；出于某种原因，我认为我的memo矩阵没有正确更新？我觉得问题正盯着我看，但由于某种原因我看不到它。任何帮助表示赞赏！

编辑：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]如果我print(memo)在 return 声明之前有权利，我会得到[[1, 1, 2], [1, 1, 2], [1, 1, 2]]. 这恰好给了我正确的答案，但memo矩阵是错误的！

标签： pythonalgorithm

解决方案

您的代码是正确的，必须根据以下内容更新 1 行：

    def uniquePathsWithObstacles(self, obstacleGrid):
    # obstruction at the start
    if (obstacleGrid[0][0] == 1): return 0
    # obstruction at the end
    if (obstacleGrid[-1][-1] == 1): return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    memo = [[0] * n for i in range(m)]
    # starting move
    memo[0][0] = 1
    # now check the first row
    for j in range(1, n):
        #memo[0][j] = 1 if (obstacleGrid[0][j] == 0 and memo[0][j-1] != 0) else 0
        memo[0][j] = 1 if (obstacleGrid[0][j] == 0 and memo[0][j-1] != 0) else 0
    # now check the first column
    for i in range(1, m):
        memo[i][0] = 1 if (obstacleGrid[i][0] == 0 and memo[i-1][0] != 0) else 0
    # now check everything else
    for i in range(1, m):
        for j in range(1, n):
            if (obstacleGrid[i][j] == 1): memo[i][j] = 0
            else: memo[i][j] = memo[i-1][j] + memo[i][j-1]
    return memo[-1][-1]

推荐阅读