1 point

# Flood Fill Algorithm: Like the bucket tool in Paint app but for multi-dimensional arrays

Thu Dec 26 2019 19:01:13 GMT+0000 (UTC)

```import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

class Pair {
int x, y;

public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}

class FloodFill
{
// Below arrays details all 8 possible movements
private static final int[] row = { -1, -1, -1, 0, 0, 1, 1, 1 };
private static final int[] col = { -1, 0, 1, -1, 1, -1, 0, 1 };

// check if it is possible to go to pixel (x, y) from
// current pixel. The function returns false if the pixel
// has different color or it is not a valid pixel
public static boolean isSafe(char[][] M, int m, int n,
int x, int y, char target)
{
return x >= 0 && x < m && y >= 0 && y < n
&& M[x][y] == target;
}

// Flood fill using BFS
public static void floodfill(char[][] M, int x, int y, char replacement)
{
int m = M.length;
int n = M[0].length;

// create a queue and enqueue starting pixel
Queue<Pair> q = new ArrayDeque<>();

// get target color
char target = M[x][y];

// run till queue is not empty
while (!q.isEmpty())
{
// pop front node from queue and process it
Pair node = q.poll();

// (x, y) represents current pixel
x = node.x;
y = node.y;

// replace current pixel color with that of replacement
M[x][y] = replacement;

// process all 8 adjacent pixels of current pixel and
// enqueue each valid pixel
for (int k = 0; k < row.length; k++)
{
// if adjacent pixel at position (x + row[k], y + col[k]) is
// a valid pixel and have same color as that of current pixel
if (isSafe(M, m, n, x + row[k], y + col[k], target))
{
q.add(new Pair(x + row[k], y + col[k]));
}
}
}
}

public static void main(String[] args)
{
// matrix showing portion of the screen having different colors
char[][] M = {
"YYYGGGGGGG".toCharArray(),
"YYYYYYGXXX".toCharArray(),
"GGGGGGGXXX".toCharArray(),
"WWWWWGGGGX".toCharArray(),
"WRRRRRGXXX".toCharArray(),
"WWWRRGGXXX".toCharArray(),
"WBWRRRRRRX".toCharArray(),
"WBBBBRRXXX".toCharArray(),
"WBBXBBBBXX".toCharArray(),
"WBBXXXXXXX".toCharArray()
};

// start node
int x = 3, y = 9;   // target color = "X"

// replacement color
char replacement = 'C';

// replace target color with replacement color
floodfill(M, x, y, replacement);

// print the colors after replacement
for (int i = 0; i < M.length; i++) {
System.out.println(Arrays.toString(M[i]));
}
}
}```
content_copy Copy

Flood fill is an algorithm mainly used to determine a bounded area connected to a given node in a multi-dimensional array. It is a close resemblance to the bucket tool in paint programs. The most approached implementation of the algorithm is a stack-based recursive function

https://www.techiedelight.com/flood-fill-algorithm/