Problem Statement
Digital Paint Bucket Tool
You're developing a new digital art application called "PixelPerfect" that allows users to create pixel art. One of the essential tools in any digital art software is the paint bucket (or fill) tool, which fills a connected area with a new color.
When a user clicks on a pixel in the canvas, the paint bucket tool should change the color of that pixel and all adjacent pixels of the same color, continuing until no more connected pixels of the original color remain.
Your task is to implement the flood fill algorithm that powers this paint bucket tool. The algorithm should efficiently fill the connected region with the new color while ensuring that only pixels of the original color are changed.
Examples
Example 1:
Input: canvas = [
['R', 'R', 'R', 'R'],
['R', 'B', 'B', 'R'],
['R', 'B', 'B', 'R'],
['R', 'R', 'R', 'R']
]
startRow = 1, startCol = 1, newColor = 'G'
Output: [
['R', 'R', 'R', 'R'],
['R', 'G', 'G', 'R'],
['R', 'G', 'G', 'R'],
['R', 'R', 'R', 'R']
]
Explanation: Starting from position (1,1) with color 'B', we fill all connected 'B' pixels with 'G'.
Example 2:
Input: canvas = [
['Y', 'Y', 'Y'],
['Y', 'Y', 'Y'],
['Y', 'Y', 'Y']
]
startRow = 0, startCol = 0, newColor = 'P'
Output: [
['P', 'P', 'P'],
['P', 'P', 'P'],
['P', 'P', 'P']
]
Explanation: Since all pixels are the same color and connected, the entire canvas is filled with the new color.
Example 3:
Input: canvas = [
['R', 'G', 'B'],
['G', 'R', 'G'],
['B', 'G', 'R']
]
startRow = 1, startCol = 1, newColor = 'Y'
Output: [
['R', 'G', 'B'],
['G', 'Y', 'G'],
['B', 'G', 'R']
]
Explanation: Starting from position (1,1) with color 'R', only that single pixel changes to 'Y' because none of its adjacent pixels have the same original color.
Constraints
- The canvas is represented as a 2D array of characters, where each character represents a color.
- The canvas dimensions m × n will be within the range [1, 50].
- The starting position (startRow, startCol) will be within the bounds of the canvas.
- The new color will be different from the original color at the starting position.
- The flood fill should only change pixels that are the same color as the starting pixel and are connected to it (horizontally or vertically, not diagonally).
Problem Breakdown
To solve this problem, we need to:
- This problem is a classic application of the Depth-First Search (DFS) pattern in recursion.
- The recursive approach naturally handles the exploration of connected pixels.
- We need to be careful not to revisit pixels we've already processed to avoid infinite recursion.
- The algorithm can also be implemented iteratively using a queue (BFS) or stack (DFS), but the recursive approach is often more intuitive.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Digital Paint Bucket Tool
You're developing a new digital art application called "PixelPerfect" that allows users to create pixel art. One of the essential tools in any digital art software is the paint bucket (or fill) tool, which fills a connected area with a new color.
When a user clicks on a pixel in the canvas, the paint bucket tool should change the color of that pixel and all adjacent pixels of the same color, continuing until no more connected pixels of the original color remain.
Your task is to implement the flood fill algorithm that powers this paint bucket tool. The algorithm should efficiently fill the connected region with the new color while ensuring that only pixels of the original color are changed.
Examples
Example 1:
Starting from position (1,1) with color 'B', we fill all connected 'B' pixels with 'G'.
Example 2:
Since all pixels are the same color and connected, the entire canvas is filled with the new color.
Example 3:
Starting from position (1,1) with color 'R', only that single pixel changes to 'Y' because none of its adjacent pixels have the same original color.
Problem Breakdown
Constraints:
- The canvas is represented as a 2D array of characters, where each character represents a color.
- The canvas dimensions m × n will be within the range [1, 50].
- The starting position (startRow, startCol) will be within the bounds of the canvas.
- The new color will be different from the original color at the starting position.
- The flood fill should only change pixels that are the same color as the starting pixel and are connected to it (horizontally or vertically, not diagonally).
Key Insights:
This problem is a classic application of the Depth-First Search (DFS) pattern in recursion.
The recursive approach naturally handles the exploration of connected pixels.
We need to be careful not to revisit pixels we've already processed to avoid infinite recursion.
The algorithm can also be implemented iteratively using a queue (BFS) or stack (DFS), but the recursive approach is often more intuitive.
Real-World Application
This problem has several practical applications:
Digital Art Software
Paint bucket tools in applications like Photoshop, GIMP, and MS Paint use flood fill algorithms.
Image Processing
Flood fill is used in image segmentation, object detection, and boundary extraction in computer vision.
Game Development
Used in games for map generation, territory control visualization, and path finding.