Flood Fill

🏠 ⬅️ ➡️

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color. Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Output: [[0,0,0],[0,0,0]] Explanation: The starting pixel is already colored 0, so no changes are made to the image.

Constraints:

  • m == image.length
  • n == image[i].length
  • 1 <= m, n <= 50
  • 0 <= image[i][j], color < 216
  • 0 <= sr < m
  • 0 <= sc < n
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: m = 3, n = 3
    integer, dimension(m, n) :: image
    integer :: sr, sc, color

    ! Example 1
    image = reshape([1, 1, 1, &
                      1, 1, 0, &
                      1, 0, 1], shape(image))
    sr = 1; sc = 1; color = 2
    call flood_fill(image, sr, sc, color)
    write(*, '(A)') 'Example 1:'
    write(*, '(A)') 'Before:'
    call print_image(image)
    write(*, '(A)') 'After:'
    call print_image(image)
    write(*, *)

    ! Example 2
    image = reshape([0, 0, 0, &
                      0, 0, 0], shape(image))
    sr = 0; sc = 0; color = 0
    call flood_fill(image, sr, sc, color)
    write(*, '(A)') 'Example 2:'
    write(*, '(A)') 'Before:'
    call print_image(image)
    write(*, '(A)') 'After:'
    call print_image(image)
    write(*, *)

contains

    subroutine flood_fill(image, sr, sc, color)
        implicit none
        integer, intent(inout) :: image(:, :)
        integer, intent(in) :: sr, sc, color
        integer :: i, j

        if (image(sr, sc) /= color) then
            return
        end if

        do i = 1, size(image, 1)
            do j = 1, size(image, 2)
                if (image(i, j) == color) then
                    image(i, j) = color
                end if
            end do
        end do

        do i = 1, size(image, 1) - 1
            do j = 1, size(image, 2) - 1
                if (image(i, j) == color .and. &
                    image(i + 1, j) == color .and. &
                    image(i, j + 1) == color .and. &
                    image(i + 1, j + 1) == color) then
                    call flood_fill(image, i, j, color)
                end if
            end do
        end do

    end subroutine flood_fill

    subroutine print_image(image)
        implicit none
        integer, intent(in) :: image(:, :)
        integer :: i, j

        do i = 1, size(image, 1)
            do j = 1, size(image, 2)
                write(*, '(I0)', advance='no') image(i, j)
            end do
            write(*, *)
        end do

    end subroutine print_image

end program main
❌ Compiled
❌ Executed
❌ Correct 
module flood_fill
    implicit none

contains

    subroutine flood_fill_helper(image, sr, sc, color)
        integer, dimension(:, :), intent(inout) :: image
        integer, intent(in) :: sr, sc, color

        ! Local variables
        integer :: m, n, i, j, new_color

        ! Get the size of the image
        m = size(image, 1)
        n = size(image, 2)

        ! Initialize the new color
        new_color = color

        ! Check if the starting pixel is already the same color as the new color
        if (image(sr, sc) == new_color) then
            return
        end if

        ! Perform the flood fill
        call flood_fill_recursive(image, sr, sc, new_color, m, n)

    end subroutine flood_fill_helper

    recursive subroutine flood_fill_recursive(image, sr, sc, new_color, m, n)
        integer, dimension(:, :), intent(inout) :: image
        integer, intent(in) :: sr, sc, new_color, m, n

        ! Local variables
        integer :: i, j

        ! Check if the starting pixel is out of bounds
        if (sr < 0 .or. sr >= m .or. sc < 0 .or. sc >= n) then
            return
        end if

        ! Check if the starting pixel is already the same color as the new color
        if (image(sr, sc) == new_color) then
            return
        end if

        ! Change the color of the starting pixel
        image(sr, sc) = new_color

        ! Recursively flood fill the neighboring pixels
        call flood_fill_recursive(image, sr - 1, sc, new_color, m, n)
        call flood_fill_recursive(image, sr + 1, sc, new_color, m, n)
        call flood_fill_recursive(image, sr, sc - 1, new_color, m, n)
        call flood_fill_recursive(image, sr, sc + 1, new_color, m, n)

    end subroutine flood_fill_recursive

end module flood_fill

program main
    use flood_fill
    implicit none

    ! Test case 1
    integer, parameter :: m = 3, n = 3, sr = 1, sc = 1, color = 2
    integer, dimension(m, n) :: image
    image = reshape((/ 1, 1, 1, &
                       1, 1, 0, &
                       1, 0, 1 /), shape(image))
    call flood_fill_helper(image, sr, sc, color)
    write (*, *) image

    ! Test case 2
    integer, parameter :: m = 2, n = 2, sr = 0, sc = 0, color = 0
    integer, dimension(m, n) :: image
    image = reshape((/ 0, 0, &
                       0, 0 /), shape(image))
    call flood_fill_helper(image, sr, sc, color)
    write (*, *) image

end program main
🌐 Data from online sources 
def floodFill(image, sr, sc, newColor):
    startColor = image[sr][sc]
    def fill(sr, sc):
        if not (0 <= sr < len(image)) or not (0 <= sc < len(image[0])) or image[sr][sc] != startColor or image[sr][sc] == newColor: 
            return
        image[sr][sc] = newColor
        fill(sr - 1, sc)
        fill(sr + 1, sc)
        fill(sr, sc - 1)
        fill(sr, sc + 1)

    fill(sr, sc)
    return image

To implement the flood-fill algorithm, we create a `fill` function that receives the image, the target position, the new color, and the starting color. It is not necessary to pass the image every time, because it's mutable, but we require the other parameters each time. We then check if the current position is out of bounds or if the current pixel color at the position is not the same as the starting color or if the current pixel color is equal to the new color. If any of these conditions are met, we return without modifying the image. Otherwise, we set the color of the current pixel to the new color and call `fill` function recursively for each adjacent 4-directionally connected pixel. The main function first sets the `startColor` as the color of the pixel image[sr][sc] and then executes the `fill` function with `sr`, `sc`, `newColor`, and `startColor`. Finally, the modified image is returned.
🌐 Data from online sources 
#include<vector>
using namespace std;

void fill(vector<vector<int>>& image, int sr, int sc, int newColor, int startColor) {
    if (sr < 0 || sc < 0 || sr >= image.size() || sc >= image[0].size() || image[sr][sc] != startColor || image[sr][sc] == newColor) return;
    image[sr][sc] = newColor;
    fill(image, sr - 1, sc, newColor, startColor);
    fill(image, sr + 1, sc, newColor, startColor);
    fill(image, sr, sc - 1, newColor, startColor);
    fill(image, sr, sc + 1, newColor, startColor);
}

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    int startColor = image[sr][sc];
    fill(image, sr, sc, newColor, startColor);
    return image;
}

To implement the flood-fill algorithm, we create a `fill` function that receives the image, the target position, the new color, and the starting color. It is not necessary to pass the image every time, because it's mutable, but we require the other parameters each time. We then check if the current position is out of bounds or if the current pixel color at the position is not the same as the starting color or if the current pixel color is equal to the new color. If any of these conditions are met, we return without modifying the image. Otherwise, we set the color of the current pixel to the new color and call `fill` function recursively for each adjacent 4-directionally connected pixel. The main function first sets the `startColor` as the color of the pixel image[sr][sc] and then executes the `fill` function with `sr`, `sc`, `newColor`, and `startColor`. Finally, the modified image is returned.