PIXELBANKv8.2.1
Menu
Sign In

Flood Fill

EasyImage Segmentation

Implement a flood fill algorithm on a given 2D grid, starting from a specified position (sr,sc)(sr, sc), to replace all connected pixels with the same original value with a new value. The connection between pixels is defined by 4-connectivity, where two pixels are considered connected if they are adjacent horizontally or vertically.

The flood fill operation is a fundamental concept in image segmentation, which is crucial in computer vision for separating objects or regions of interest from the rest of the image. This process can be viewed as a graph traversal problem, where each pixel represents a node, and the connections between them are edges. The goal is to traverse the graph, starting from a given node, and update all connected nodes that share the same original value.

Here are the steps to achieve this:

  1. Identify the starting position (sr,sc)(sr, sc) and the new value.
  2. Determine the original value of the starting pixel.
  3. Check if the starting pixel already has the new value.
  4. Traverse the grid, updating all connected pixels with the same original value.
Connected pixels: (r,c) and (r′,c′) if ∣r−r′∣+∣c−c′∣=1\text{Connected pixels: } (r, c) \text{ and } (r', c') \text{ if } |r-r'| + |c-c'| = 1

This technique is widely used in image editing software.

Example:

Input:
grid = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
sr = 1, sc = 1, new_val = 2
Output:
[[2, 2, 2], [2, 2, 0], [2, 0, 1]]
Reasoning:
  • The algorithm starts at the given position (sr, sc) = (1, 1) and checks its value, which is 1.
  • Since the new value (2) is different from the current value (1), it replaces the current value with the new value and recursively checks adjacent pixels (up, down, left, right) that have the same original value (1).
  • The adjacent pixels to (1, 1) that have the value 1 are (0, 0), (0, 1), (0, 2), (1, 0), (1, 2), and (2, 1), and (2, 0) does not have the value 1 but (2, 1) does, so it replaces their values with 2.
  • The final output is [[2, 2, 2], [2, 2, 0], [2, 0, 1]] after all connected pixels with the original value 1 have been replaced with the new value 2.

Constraints:

  • grid is a 2D list of integers
  • (sr, sc) is a valid position in the grid
  • new_val is an integer
  • Use 4-connectivity (up, down, left, right)
  • Return the modified grid
Editor

Test Results

0/0
Run code to see test results.