Flood Fill
Given a 2D image grid, a starting pixel (sr, sc), and a new color, perform a flood fill — change the starting pixel and all connected same-colored pixels to the new color.
Output the resulting grid, each row on a new line, values space-separated.
Example:
1,1,1 1,1,0 1,0,1 1 1 2
2 2 2 2 2 0 2 0 1
- The input image grid is: 1 1 1 1 1 0 1 0 1 with a starting pixel at position (1, 1) and a new color of 2.
- We start the flood fill from the pixel at position (1, 1) with a value of 1 and replace it with the new color 2.
- All adjacent pixels with the same color (1) are also replaced with the new color 2, which includes the pixels at positions (0, 0), (0, 1), (0, 2), (1, 0), and (2, 0), (2, 1).
- The resulting grid after the flood fill operation is: 2 2 2 2 2 0 2 0 1
Constraints:
- 1 <= rows, cols <= 50
- 0 <= image[i][j], color <= 65535
Background Knowledge
The Flood Fill problem is a classic example of a graph traversal problem, where we need to visit all connected nodes (pixels) in a grid. To understand this problem, we need to know the basics of graph theory, including nodes (pixels), edges (connections between pixels), and traversal algorithms. In this case, we're dealing with a 2D grid, where each pixel is connected to its neighbors (up, down, left, right, and possibly diagonally).
The key concept here is connectedness, which means that two pixels are connected if they have the same color and are adjacent to each other. We need to find all connected pixels to the starting pixel (sr, sc) and change their color to the new color. This problem can be solved using various graph traversal algorithms, such as Depth-First Search (DFS) or Breadth-First Search (BFS). Understanding the differences between these algorithms and how to apply them to a grid is crucial to solving this problem.
In the context of image processing, flood fill is a fundamental operation used in various applications, such as image editing, computer vision, and graphics. It's essential to understand how to efficiently traverse a grid and update pixel values, which is a critical skill in many areas of computer science.
Algorithm/Approach
The general approach to solving this problem involves using a graph traversal algorithm to visit all connected pixels to the starting pixel. The algorithm should start at the given pixel (sr, sc) and explore all neighboring pixels that have the same color. Once all connected pixels are visited, we can update their color to the new color. The choice of traversal algorithm (DFS or BFS) depends on the specific requirements of the problem and the desired outcome.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.