CODEWITHSUNDEEP
python-3.x
Wei Bovey
Wei Bovey

Reputation: 33

Unique Paths II

A robot is located at the top-left corner of a m x n grid.

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.

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

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

class Solution:
    """
    @param obstacleGrid: A list of lists of integers
    @return: An integer
    """
    def uniquePathsWithObstacles(self, obstacleGrid):
        # write your code here
        if not obstacleGrid:
            return 0

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        li = [[0] * n] * m

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    li[i][j] = 0 ######## why do I have to add this line ???########
                    continue
                elif i == 0 and j == 0:
                    li[i][j] = 1
                elif i == 0:
                    li[i][j] = li[i][j - 1]
                elif j == 0:
                    li[i][j] = li[i - 1][j]
                else:
                    li[i][j] = li[i - 1][j] + li[i][j - 1]

        return li[m - 1][n - 1]

The question is in the coding. I already set the matrix of m*n filling with zeros. Why should I assign the zero to the position one more time??? It seems that it won't work if I del that line. Can anyone tell me the reason why??? Thx!!!

Upvotes: 0

Views: 61

Answers (1)

c2huc2hu
c2huc2hu

Reputation: 2497

The problem is this line: 

li = [[0] * n] * m

The syntax [a] * n creates shallow copies, not deep copies of a.

Example: 

n = m = 2
li[0][0] = 3
print(li)  # prints [[3, 0], [3, 0]]

Link to question with discussion of possible solutions.

Upvotes: 1

Related Questions