I think I misunderstand some important concepts in Python and it is not specific to the Leetcode problem. I greatly appreciate for any help from who knows Python deeply.
The Leetcode 542 is that given a 2D array consisting of 0 and 1 only, and for each 1, find the shortest distance to reach 0. I have a dummy DFS solution:
class Solution:
def updateMatrix(self, matrix):
dists = []
for _ in range(len(matrix)):
dists.append([0]*len(matrix[0]))
for y in range(len(matrix)):
for x in range(len(matrix[0])):
if matrix[y][x] == 1:
self.min_dist = len(matrix)+len(matrix[0])
self.DFS(x, y, matrix, 0, set({}))
dists[y][x] = self.min_dist
return dists
def DFS(self, x, y, matrix, distance, visited):
if (x, y) in visited or (matrix[y][x] == 1 and distance > self.min_dist): return
if matrix[y][x] == 0:
print (x, y, "d:", distance)
print ('------')
self.min_dist = min(self.min_dist, distance)
return
print (x, y, distance)
visited.add((x, y))
if x > 0 and (x-1, y) not in visited:
self.DFS(x-1, y, matrix, distance+1, visited)
if y > 0 and (x, y-1) not in visited:
self.DFS(x, y-1, matrix, distance+1, visited)
if x < len(matrix[0])-1 and (x+1, y) not in visited:
self.DFS(x+1, y, matrix, distance+1, visited)
if y < len(matrix)-1 and (x, y+1) not in visited:
self.DFS(x, y+1, matrix, distance+1, visited)
Simply DFS until reaching 0. Every time we call DFS, distance + 1. It looks good to me. But a test case input = [[1,0,0],[0,1,1],[1,1,1]] gives me dist = [[1,0,0],[0,1,1],[1,2,3]].
If change matrix[y][x] == 1 to matrix[y][x] == 1 and x==2 and y==2 and run the above code, the output is
2 2 0
1 2 1
0 2 2
0 1 d: 3
------
1 1 2
0 1 d: 3
------
1 0 d: 3
------
2 1 3
2 0 d: 4
------
At (x,y)= (2,1) the initial distance is changed to 3. but the initial distance at (2,1) should be 1. My question is why it changes? Can anyone help me point out where I did wrong? Thanks!
Been taking a look at this. It seems the problem is the way the visited set is modified. I think it's being passed by reference which means by the time it tries to go (2,2) -> (2,1) the set already contains the point (2,1), i.e the preceding DFS paths have added all their points to it.
I found this article explains "Pass By Reference in Python" well - https://realpython.com/python-pass-by-reference/.
I got your test case to pass by always passing down visited.copy(), i.e self.DFS(x-1, y, matrix, distance+1, visited.copy()). I'm not a Python expert and imagine there are cleaner ways to handle this though.