Guided Project: Graphs III

What is Floodfill?

Core Concepts

Graph traversal algorithm
Fills connected regions
Uses DFS or BFS approach
4-way or 8-way connectivity

Applications

Paint bucket tool
Image segmentation
Game map exploration
Maze solving

Visual Example

Before Floodfill

1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1

After Floodfill (start at [1,1])

1 1 1 1 1 1 2 2 2 1 1 2 2 2 1 1 1 1 1 1

Step-by-Step Implementation

Implementation Steps

                                    function floodFill(grid, row, col, newColor, oldColor = grid[row][col]) {
    // Check bounds and color match
    if (row < 0 || row >= grid.length || 
        col < 0 || col >= grid[0].length || 
        grid[row][col] !== oldColor) {
        return;
    }

    // Fill current cell
    grid[row][col] = newColor;

    // Recursively fill neighbors (4-way connectivity)
    floodFill(grid, row + 1, col, newColor, oldColor);  // Down
    floodFill(grid, row - 1, col, newColor, oldColor);  // Up
    floodFill(grid, row, col + 1, newColor, oldColor);  // Right
    floodFill(grid, row, col - 1, newColor, oldColor);  // Left
}
                                

Example Usage

                                    const grid = [
    [1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
];

// Fill starting at [1,1] with color 2
floodFill(grid, 1, 1, 2);

console.log(grid);
/* Output:
[
    [1, 1, 1, 1, 1],
    [1, 2, 2, 2, 1],
    [1, 2, 2, 2, 1],
    [1, 1, 1, 1, 1]
]
*/
                                

Iterative Implementation (using BFS)

                                    function floodFillBFS(grid, row, col, newColor) {
    const oldColor = grid[row][col];
    if (oldColor === newColor) return grid; // No need to fill if same color
    
    const queue = [[row, col]];
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // Down, Up, Right, Left
    
    while (queue.length > 0) {
        const [r, c] = queue.shift();
        
        // Check if this cell needs filling
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] !== oldColor) {
            continue;
        }
        
        // Fill current cell
        grid[r][c] = newColor;
        
        // Add all adjacent cells to queue
        for (const [dr, dc] of directions) {
            queue.push([r + dr, c + dc]);
        }
    }
    
    return grid;
}
                                

Practice Challenge: 8-Way Floodfill

Challenge Description

Implement a floodfill algorithm that uses 8-way connectivity (includes diagonals).

Requirements:

Modify the floodfill algorithm to include diagonal neighbors
Add an additional parameter to toggle between 4-way and 8-way connectivity
Test with various grid patterns

Code Starting Point

                                function floodFill(grid, row, col, newColor, useEightWay = false, oldColor = grid[row][col]) {
    // Check bounds and color match
    if (row < 0 || row >= grid.length || 
        col < 0 || col >= grid[0].length || 
        grid[row][col] !== oldColor) {
        return;
    }

    // Fill current cell
    grid[row][col] = newColor;

    // Recursively fill neighbors (4-way connectivity)
    floodFill(grid, row + 1, col, newColor, useEightWay, oldColor);  // Down
    floodFill(grid, row - 1, col, newColor, useEightWay, oldColor);  // Up
    floodFill(grid, row, col + 1, newColor, useEightWay, oldColor);  // Right
    floodFill(grid, row, col - 1, newColor, useEightWay, oldColor);  // Left
    
    // TODO: Add diagonal directions for 8-way connectivity
    // if (useEightWay) {
    //     ...
    // }
}
                            

Testing Your Solution

                                // Create a test grid
const grid1 = [
    [1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
];

// Test with 4-way connectivity
const grid2 = JSON.parse(JSON.stringify(grid1)); // Deep copy
floodFill(grid2, 1, 1, 2, false);
console.log("4-way result:");
console.log(grid2);

// Test with 8-way connectivity
const grid3 = JSON.parse(JSON.stringify(grid1)); // Deep copy
floodFill(grid3, 1, 1, 2, true);
console.log("8-way result:");
console.log(grid3);
                            

LeetCode Practice

After completing this challenge, try these LeetCode problems:

733. Flood Fill - Basic floodfill implementation
200. Number of Islands - Count connected regions
130. Surrounded Regions - Advanced floodfill application

Guided Project: Floodfill Algorithm