194. Flood Fill Algorithm

Given a grid of integers, a starting cell, and a new color, replace the color of every cell in the starting cell's connected region (4-directionally connected cells sharing the starting cell's original color) with the new color. Print the resulting grid, one row per line, space-separated.

Input: The first line contains two integers rows and cols. The next rows lines each contain cols space-separated integers representing the grid. The next line contains two integers, the starting cell's row and column. The final line contains the new color. Output: Print the resulting grid after the flood fill, rows lines each with cols space-separated integers.

1 <= rows, cols <= 1000

If the new color happens to equal the original color, the algorithm should do nothing (or it could infinite-loop if not handled carefully) - a subtle edge case worth checking explicitly in an implementation.

Replace the color of an entire connected region of a grid (starting from a given cell) with a new color. Brute force: Scan the entire grid for every cell matching the original color and change them ALL - this incorrectly changes cells of the SAME color that aren't actually CONNECTED to the starting cell, a subtle but important bug. Optimised: Flood-filling via BFS/DFS ensures only cells REACHABLE from the start through a connected path of the original color get changed - checking CONNECTIVITY (not just color-matching) is exactly what distinguishes correct flood fill from a naive 'replace all matching cells' approach.

Use the same connected-region exploration logic as the brute-force recursive version, but manage the traversal with an explicit stack data structure instead of the call stack, pushing unvisited same-colored neighbors and popping to process them. This avoids the risk of a native recursion stack overflow on large grids while visiting each cell exactly once, and gives explicit control over memory usage compared to relying on the language runtime's call stack. Time: O(rows * cols) Space: O(rows * cols)

Starting from the given cell, recursively recolor the current cell and then recurse into its four neighbors if they share the original color, stopping when a neighbor no longer matches. This directly implements the definition of flood fill, but it requires careful special-casing when the new color equals the old color (otherwise the recursion condition 'neighbor still has old color' never becomes false and it loops forever revisiting the same cells), and on a grid as large as 1000x1000 the recursion depth can be large enough to risk a stack overflow. Time: O(rows * cols) Space: O(rows * cols) recursion stack in the worst case

Explore the connected region level by level using a queue: enqueue the starting cell, and repeatedly dequeue a cell, recolor it, and enqueue any of its 4-directional neighbors that still have the original color and haven't been enqueued yet. This is the standard, robust production approach because it naturally handles the new-color-equals-old-color edge case cleanly (by marking cells as enqueued rather than relying purely on color comparison) and its memory usage tracks the current frontier of the region rather than the full recursion depth, which tends to be more predictable and bounded for wide, shallow regions. Time: O(rows * cols) Space: O(rows * cols) worst case, typically much less

1. BFS or DFS outward from the starting cell. 2. Only continue into neighbors that STILL have the ORIGINAL color (the color the starting cell had before any changes). 3. Change each visited cell's color to the new one as you go.

Time: O(rows * cols) in the worst case - every cell is visited at most once during the flood-fill. Space: O(rows * cols) in the worst case, for the BFS queue or DFS recursion stack.

rows or cols = 1 (a single row/column grid), the starting cell's color already equal to the new color, and a cell matching the original color but not 4-directionally connected to the start (must stay unchanged) - also rows and cols near 1000 to confirm the BFS/DFS runs efficiently.

Be ready to point out the exact bug that a naive 'change every cell matching the original color' approach would introduce - it's a great example of why CONNECTIVITY, not just value-matching, is the actual requirement.