[Leetcode][python] 733: flood fill - bfs

• Leetcode 733: flood fill - bfs
• Level Easy
• Link

Flood Fill - LeetCode

My Approach

Classic bfs problem with replacing existing values into the new value

1. Locate the starting number and search through up, down, left, right index.
   1. Check if the new element is within the rlength and clength
   2. Check if the new position is not visited
   3. Check if the new element is equal to the startnum
2. If the new element is equal to the startnum
   1. Append to q and visited
   2. Replace the new element with startnum

class Solution:
    
    def check(self, r, c, rlimit, climit):
        return 0 <= r < rlimit and 0 <= c < climit
    
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        
        # locate starting number
        startnum = image[sr][sc]
        image[sr][sc] = newColor
        q = []
        visited = []
        q.append((sr, sc))
        visited.append((sr, sc))
        
        dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
        
        while q:
            qr, qc = q.pop()
            # set new direction
            for dir in range(4):
                nr = qr + dr[dir]
                nc = qc + dc[dir]
                # check for index validity
                if (nr, nc) not in visited and self.check(nr, nc, len(image), len(image[0])):
                    # if the new element is equal to startnum
                    if image[nr][nc] == startnum:
                        # append to visited and q
                        visited.append((nr, nc))
                        q.append((nr, nc))
                        # change new element to newcolor
                        image[nr][nc] = newColor
                        
        return (image)