Flood Fill

# Flood Fill ## Difficulty Easy ## Tags `graph`, `dfs`, `bfs`, `matrix` ## Problem Statement An image is represented by an `m x n` integer grid `image` where `image[i][j]` represents the pixel value. You are given three integers `sr`, `sc`, and `new_color`. Perform a **flood fill** starting from pixel `image[sr][sc]`. To perform a flood fill: 1. Start at the pixel `image[sr][sc]`. 2. Change its color to `new_color`. 3. Repeat for all pixels connected 4-directionally (up, down, left, right) that have the same original color. Return the modified image. ## Constraints - m == image.length - n == image[i].length - 1 ≤ m, n ≤ 50 - 0 ≤ image[i][j], new_color < 2¹⁶ - 0 ≤ sr < m - 0 ≤ sc < n ## Signatures ### Python ```python def flood_fill(image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]: pass ``` ### Java ```java public class Solution { public List<List<Integer>> flood_fill(List<List<Integer>> image, int sr, int sc, int new_color) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<IList<int>> flood_fill(IList<IList<int>> image, int sr, int sc, int new_color) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<vector<int>> flood_fill(vector<vector<int>> image, int sr, int sc, int new_color) { } }; ``` ### C ```c vector<int*> flood_fill(vector<int*> image, int sr, int sc, int new_color) { } ``` ### Ruby ```ruby def flood_fill(image, sr, sc, new_color) end ``` ### Perl ```perl sub flood_fill { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def flood_fill(image: List[List[Int]], sr: Int, sc: Int, new_color: Int): List[List[Int]] = { } } ``` ### Haskell ```haskell flood_fill :: ... -> ... flood_fill args = undefined ``` ### Clojure ```clojure (defn flood_fill [image sr sc new_color] ) ``` ### Scheme ```scheme (define (flood_fill image sr sc new_color) ) ``` ## Examples ### Example 1 **Input:** ``` image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1 sc = 1 new_color = 2 ``` **Output:** ``` [[2,2,2],[2,2,0],[2,0,1]] ``` **Explanation:** Starting at (1,1) with color 1, all connected pixels with color 1 are changed to 2. The pixel at (1,2) is 0, so it's not changed. The pixel at (2,2) is 1 but not connected to the starting region. ### Example 2 **Input:** ``` image = [[0,0,0],[0,0,0]] sr = 0 sc = 0 new_color = 0 ``` **Output:** ``` [[0,0,0],[0,0,0]] ``` **Explanation:** The new_color is the same as the original, so no change is made. ## Hints 1. Use DFS or BFS to traverse connected pixels. 2. Be careful to avoid infinite loops when `new_color` equals the original color. 3. Check bounds before accessing neighboring pixels.