Issue solving DFS Flood Fill problem while iterating through branching options

Question

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.

Answer 1

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:

• In the first version ((-1,0),(0, -1)... directions) sr stays 0 after sr = sr + direc[0] since previous sr is 0 and current direc is (0,-1).
• In the second version ((sr-1, sc),(sr, sc-1)... directions) 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.