• 注册
    • 查看作者
    • leetcode: 63. Unique Paths II

      63. Unique Paths II

      Medium


      A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

      The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

      Now consider if some obstacles are added to the grids. How many unique paths would there be?

      leetcode: 63. Unique Paths II

      An obstacle and empty space is marked as 1 and 0 respectively in the grid.

      Note: m and n will be at most 100.

      Example 1:

      Input:[
        [0,0,0],
        [0,1,0],
        [0,0,0]
      ]Output: 2Explanation:There is one obstacle in the middle of the 3x3 grid above.
      There are two ways to reach the bottom-right corner:
      1. Right -> Right -> Down -> Down
      2. Down -> Down -> Right -> Right
      class Solution:
          def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
              
              
              if obstacleGrid[0][0] == 1:
                  return 0
              n = len(obstacleGrid)
              m =len(obstacleGrid[0])
              for i in range(n):
                  for j in range(m):
                      if obstacleGrid[i][j] == 1:
                          obstacleGrid[i][j] = 'x'
                          
              j= 0
              while  j < m and obstacleGrid[0][j] is not 'x' :
                  obstacleGrid[0][j] = 1
                  j +=1
                  print(n)
                  
              i=0
              while i < n and obstacleGrid[i][0] is not 'x'  :
                  obstacleGrid[i][0] = 1
                  i+=1
              print(obstacleGrid)
              for i in range(1,n):
                  for j in range(1,m):  
                      if obstacleGrid[i][j] is not 'x':
                          if obstacleGrid[i-1][j] is 'x':
                              obstacleGrid[i][j] = obstacleGrid[i][j-1]
                          elif obstacleGrid[i][j-1] is 'x':
                              obstacleGrid[i][j] = obstacleGrid[i-1][j]
                          else:
                              obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
              if obstacleGrid[n-1][m-1] == 'x':
                  return 0        
              return obstacleGrid[n-1][m-1]

                          

       The same thought as 62, here is the link.

       the different is thinking about the situation below:

      1. 'x' block in the middle. sol: do not add the x just copy the upper value

      1 1 1 1 1 1 1
      x 1
      0

      2. 'x' block in the middle. sol: do not add the x just copy the left value

      1 x 1 1 1 1 1
      1 1
      1

      3. There are not starting point, return 0

      x 1 1 1 1 1 1
      1
      1

      4. There are not ending point, return 0

      1 1 1 1 1 1 1
      1
      1 x

      5. There are 'x' block the whole column, there will 

      be not additional calculation the right, return 0

      1 1 x
      1 x
      1 x

      6. The start is the ending, return 1

      1

      纽约州·法拉盛
    • 0
    • 0
    • 0
    • 949
    • 请登录之后再进行评论

      登录
    • 做任务