LeetCode 733. Flood Fill (Python)

LeetCode 733 is a problem that requires you to implement the flood fill algorithm. This algorithm is used in computer graphics to fill a region with a specific color. In this problem, you are given a 2D array representing a pixel grid, and you need to fill the grid with a specific color, starting from a given position. The position is represented by the coordinates (x, y). The fill operation follows these rules: if the pixel at (x, y) is the same as the target color, it remains unchanged; otherwise, it is changed to the target color. The fill operation then recursively propagates in all four directions (up, down, left, right) until it encounters a pixel that cannot be changed or has already been filled. The algorithm then backtracks to the previous pixel and continues filling in the other direction. This process continues until all reachable pixels are filled with the target color.

Here’s a Python implementation of the flood fill algorithm for LeetCode 733:

def flood_fill(image, x, y, new_color):
    original_color = image[x][y]
    if original_color == new_color:
        return
    if x < 0 or y < 0 or x >= len(image) or y >= len(image[0]) or image[x][y] != original_color:
        return
    image[x][y] = new_color
    flood_fill(image, x - 1, y, new_color)
    flood_fill(image, x + 1, y, new_color)
    flood_fill(image, x, y - 1, new_color)
    flood_fill(image, x, y + 1, new_color)
# Example usage
image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
x = 1
y = 1
new_color = 2
flood_fill(image, x, y, new_color)
print(image)

In this example, we define the flood_fill function that takes the image, starting position (x, y), and the new color as input. It first checks if the starting pixel has the same color as the target color. If so, there’s no need to fill the region, and the function returns immediately. Otherwise, it checks if the starting pixel is within the boundaries of the image and if it has the original color. If any of these conditions are not met, the function returns immediately as well. Otherwise, it changes the color of the starting pixel to the target color and recursively calls itself in all four directions (up, down, left, right). The function continues this process until all reachable pixels are filled with the target color.

Note that this implementation assumes that the input image is a list of lists representing a square grid of pixels. Each pixel is represented by an integer value. The function modifies the input image in-place and returns nothing. You can use this implementation to solve LeetCode 733 and similar problems related to flood fill.

Remember to adjust the example usage code according to your specific requirements and test cases.