欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

63. 不同路径 II

程序员文章站 2022-07-16 12:00:38
...

63. 不同路径 II
63. 不同路径 II

解1 递归

dfs深度优先
超出时间限制

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        
        if obstacleGrid == []:
            return 0
        
        if obstacleGrid[0][0] == 1:
            return 0
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[m - 1][n - 1] == 1:
            return 0
        
        result = list()
        self.dfs(obstacleGrid, 0, 0, result)
        return sum(result)
        
        
    def dfs(self, obstacleGrid, i, j, result):
        
        if i == len(obstacleGrid) - 1 and j == len(obstacleGrid[0]) - 1:
            result.append(1)
            
        elif i == len(obstacleGrid) - 1:
            if obstacleGrid[i][j + 1] == 1:
                return
            else:
                self.dfs(obstacleGrid, i, j + 1, result)
                
        elif j == len(obstacleGrid[0]) - 1:
            if obstacleGrid[i + 1][j] == 1:
                return
            else:
                self.dfs(obstacleGrid, i + 1, j, result)
        
        else:
            if obstacleGrid[i][j + 1] == 0:
                self.dfs(obstacleGrid, i, j + 1, result)
                
            if obstacleGrid[i + 1][j] == 0:
                self.dfs(obstacleGrid, i + 1, j, result)

解2 动态规划

参考62

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        
        if obstacleGrid == []:
            return 0
        
        # 机器人所在位置为障碍物 无法开始
        if obstacleGrid[0][0] == 1:
            return 0
        
        # 终点为障碍物 无法到达
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[m - 1][n - 1] == 1:
            return 0
        
        # 动态规划
        path = [[1 for i in range(n)] for j in range(m)]
        
        # 若第1列 有一个方格为障碍物 那么相当于它下面的方格都为障碍物
        for i in range(1, m):
            if obstacleGrid[i-1][0]:
                obstacleGrid[i][0] = 1
        
        # 同理 第一行有一个为障碍物 右边的方格都为障碍物
        for j in range(1, n):
            if obstacleGrid[0][j - 1]:
                obstacleGrid[0][j] = 1
            
        
        for i in range(1, m):
            for j in range(1, n):
                
                
                if (obstacleGrid[i - 1][j] and obstacleGrid[i][j - 1]) or obstacleGrid[i][j]:
                    # 上 左 都无法到达 或 本身就是障碍
                    path[i][j] = 0
                    
                elif obstacleGrid[i - 1][j]:
                    # 上 为障碍物
                    path[i][j] = path[i][j - 1]
                    
                elif obstacleGrid[i][j - 1]:
                    # 左 为障碍物
                    path[i][j] = path[i - 1][j]
                    
                else:
                    # 上 左 都可到达
                    path[i][j] = path[i][j - 1] + path[i - 1][j]
                    
        return path[m - 1][n - 1]