Flood Fill

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).
Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.
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 as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the new color.
In the end, return the modified image.

Example 1:

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Approach

Java

import java.util.Arrays;

public class FloodFill {
    public static void main(String[] args) {
        int[][] image = { { 111 }, { 110 }, { 101 } };
        int sr = 1, sc = 1, newColor = 2;
        image = floodFill(image, sr, sc, newColor);
        System.out.println(Arrays.deepToString(image));
    }

    static int[][] floodFill(int[][] imageint srint scint newColor) {
        int prevColor = image[sr][sc];
        dfs(image, sr, sc, prevColor, newColor);
        return image;
    }

    static void dfs(int[][] imageint xint yint prevColorint newColor) {
        // check if current cell is valid or not
        if (x < 0 || x >= image.length || y < 0 || y >= image[0].length)
            return;

        // if current cell color is not same as the
        // prev color
        if (image[x][y] != prevColor)
            return;

        // if current cell color is same as new color
        if (image[x][y] == newColor)
            return;

        // update current cell color to new color
        image[x][y] = newColor;

        // call for down
        dfs(image, x + 1, y, prevColor, newColor);

        // call for up
        dfs(image, x - 1, y, prevColor, newColor);

        // call for right
        dfs(image, x, y + 1, prevColor, newColor);

        // call for left
        dfs(image, x, y - 1, prevColor, newColor);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>> &imageint xint yint prevColorint newColor)
{
    //check if current cell is valid or not
    if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size())
        return;

    //if current cell color is not same as the
    //prev color
    if (image[x][y] != prevColor)
        return;

    //if current cell color is same as new color
    if (image[x][y] == newColor)
        return;

    //update current cell color to new color
    image[x][y] = newColor;

    //call for down
    dfs(imagex + 1yprevColornewColor);

    //call for up
    dfs(imagex - 1yprevColornewColor);

    //call for right
    dfs(imagexy + 1prevColornewColor);

    //call for left
    dfs(imagexy - 1prevColornewColor);
}
vector<vector<int>> floodFill(vector<vector<int>> &imageint sr,
         int scint newColor)
{
    int prevColor = image[sr][sc];
    dfs(imagesrscprevColornewColor);
    return image;
}

int main()
{
    vector<vector<int>> image = {{111},
                                 {110},
                                 {101}};
    int sr = 1sc = 1newColor = 2;
    image = floodFill(imagesrscnewColor);
    cout << "[";
    for (int i = 0i < image.size(); i++)
    {
        cout << "[";
        for (int j = 0j < image[i].size(); j++)
        {
            cout << image[i][j];
            if (j != image[i].size() - 1)
                cout << ", ";
        }
        cout << "]";
        if (i != image.size() - 1)
            cout << ",";
    }
    cout << "]";
    return 0;
}


No comments:

Post a Comment