I am learning Dynamic Programming and am trying to solve the Leet Code Flood Fill problem.
I came up with this solution, but it doesn't recurse correctly through all the possible moves.
Given the input image=[[1,1,1],[1,1,0],[1,0,1]] and sr=1, sc=1, and color=2. I get the incorrect response as [[2,2,1],[2,2,0],[1,0,1]]
def floodFill(
self, image: List[List[int]], sr: int, sc: int, color: int
) -> List[List[int]]:
m = len(image) - 1
n = len(image[0]) - 1
basecolor = image[sr][sc]
self.dfs(image, sr, sc, color, basecolor, m, n)
return image
def dfs(self, image, sr, sc, color, basecolor, m, n):
if sr < 0 or sr > m or sc < 0 or sc > n:
return
if image[sr][sc] == color:
return
if image[sr][sc] != basecolor:
return
image[sr][sc] = color
for direc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
sr = sr + direc[0]
sc = sc + direc[1]
self.dfs(image, sr, sc, color, basecolor, m, n)
But when I update the list in the for loop, I get the right answer [[2,2,2],[2,2,0],[2,0,1]]
def floodFill(
self, image: List[List[int]], sr: int, sc: int, color: int
) -> List[List[int]]:
m = len(image) - 1
n = len(image[0]) - 1
basecolor = image[sr][sc]
self.dfs(image, sr, sc, color, basecolor, m, n)
return image
def dfs(self, image, sr, sc, color, basecolor, m, n):
if sr < 0 or sr > m or sc < 0 or sc > n:
return
if image[sr][sc] == color:
return
if image[sr][sc] != basecolor:
return
image[sr][sc] = color
for direc in [(sr-1, sc), (sr, sc-1), (sr+1, sc), (sr, sc+1)]:
sr = direc[0]
sc = direc[1]
self.dfs(image, sr, sc, color, basecolor, m, n)
Can someone explain to me why the values of sc or sc in the for loop are causing the error? I think it might have something to do with recursion, but can't figure it out. Or maybe it is something really simple that I have overlooked.
Those loops are not equivalent, they assign sr and sc with different values.
sr = 1
sc = 1
direcs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
print('directions:', direcs)
for direc in direcs:
sr = sr + direc[0]
sc = sc + direc[1]
print('sr:{} sc:{}'.format(sr, sc))
print('-' * 30)
sr = 1
sc = 1
direcs = [(sr-1, sc), (sr, sc-1), (sr+1, sc), (sr, sc+1)]
print('directions:', direcs)
for direc in direcs:
sr = direc[0]
sc = direc[1]
print('sr:{} sc:{}'.format(sr, sc))
Output:
directions: [(-1, 0), (0, -1), (1, 0), (0, 1)]
sr:0 sc:1
sr:0 sc:0
sr:1 sc:0
sr:1 sc:1
------------------------------
directions: [(0, 1), (1, 0), (2, 1), (1, 2)]
sr:0 sc:1
sr:1 sc:0
sr:2 sc:1
sr:1 sc:2
The first mismatch occurs on a second step:
sr stays 0 after sr = sr + direc[0] since previous sr is 0 and current direc is (0,-1).sr becomes 1 after sr = direc[0]. Current direc (1, 0) was set before the loop has started using an initial sr and sc values: (sr, sc-1).As the loop continues discrepancies accumulate or cancel out.