Unique Paths II

Question

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!!!

Please [edit] the line where you say "It seems that it won't work if I del that line." This is vague. It either does work when you del that line, or it doesn't. In the first case, you've proven that the line isn't necessary, and the answer to your question boils down to "sometimes programmers write lines to assert things to the reader that were already true." In the latter case, you can rephrase your title to be more meaningful, e.g. "Why would I need to set a value to 0 that's already set to 0?" — Scott Mermelstein, Apr 05 '19 at 16:33
Of course, while you're editing, fix your formatting by putting 4 spaces in front of each line of code. And you may want to consider leading with a question instead of an assignment dump. Those usually scare people away from wanting to answer. — Scott Mermelstein, Apr 05 '19 at 16:36

score 1 · Accepted Answer · answered Apr 05 '19 at 21:19

1

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.

answered Apr 05 '19 at 21:19

c2huc2hu

2,447
17
26

Unique Paths II

1 Answers1