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<>();
q.add(new Pair(x, y));
// 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))
{
// enqueue adjacent pixel
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]));
}
}
}
Comments