What is the Flood Fill Algorithm?

The flood fill algorithm is a method used in computer graphics to determine the area that is connected to a given starting point in a multi-dimensional array. It is often used in image editing programs to “fill” an area with a certain color or pattern.

Here is an example of how the flood fill algorithm might work in C#:

// A 2D array representing an image, where each element
// represents a pixel
int[,] image = new int[10, 10];

// The starting point for the flood fill
int startX = 5;
int startY = 5;

// The color we want to fill the area with
int fillColor = 1;

// The color of the starting point
int startingColor = image[startX, startY];

// A queue of points that need to be checked
Queue<Point> pointsToCheck = new Queue<Point>();
pointsToCheck.Enqueue(new Point(startX, startY));

// Keep going until all reachable points have been checked
while (pointsToCheck.Count > 0)
{
    Point currentPoint = pointsToCheck.Dequeue();

    // Check if this point is within the bounds of the image
    // and has the same color as the starting point
    if (currentPoint.X >= 0 && currentPoint.X < image.GetLength(0) &&
        currentPoint.Y >= 0 && currentPoint.Y < image.GetLength(1) &&
        image[currentPoint.X, currentPoint.Y] == startingColor)
    {
        // Set the color of this point to the fill color
        image[currentPoint.X, currentPoint.Y] = fillColor;

        // Add the surrounding points to the queue to be checked
        pointsToCheck.Enqueue(new Point(currentPoint.X - 1, currentPoint.Y));
        pointsToCheck.Enqueue(new Point(currentPoint.X + 1, currentPoint.Y));
        pointsToCheck.Enqueue(new Point(currentPoint.X, currentPoint.Y - 1));
        pointsToCheck.Enqueue(new Point(currentPoint.X, currentPoint.Y + 1));
    }
}

In this example, the flood fill algorithm starts at the point (5, 5) and expands outward, filling any adjacent points that have the same color as the starting point with the fill color. This continues until all reachable points have been checked.