Saturday, September 18, 2021

Flood Fill 4-directional using Java

How it works?
Flood-fill (node):
  1. Set Q to the empty queue or stack.
  2. Add the current node to the end of Q.
  3. While Q is not empty:
  4.   Set n equal to the first element of Q.
  5.   Remove first element from Q.
  6.   If n is Inside:
         Set the n
         Add the node to the north of n to the end of Q.
         Add the node to the south of n to the end of Q.
         Add the node to the west of n to the end of Q.
         Add the node to the east of n to the end of Q.
  7. Continue looping until Q is exhausted.
  8. Return.

package samples;

import java.util.ArrayDeque;
import java.util.Queue;

public class FloodFill {

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {

int oldColor = image[sr][sc];
if (oldColor == newColor)
return image;

Queue<Pair> queue = new ArrayDeque();
queue.add(new Pair(sr, sc));

while (!queue.isEmpty()) {

Pair p = queue.poll();
if (isInside(image, p.i, p.j, oldColor))
set(image, p.i, p.j, newColor);

// up -> row-1
if (isInside(image, p.i - 1, p.j, oldColor))
queue.add(new Pair(p.i - 1, p.j));

// down -> row+1
if (isInside(image, p.i + 1, p.j, oldColor))
queue.add(new Pair(p.i + 1, p.j));

// left -> col-1
if (isInside(image, p.i, p.j - 1, oldColor))
queue.add(new Pair(p.i, p.j - 1));

// right -> col+1
if (isInside(image, p.i, p.j + 1, oldColor))
queue.add(new Pair(p.i, p.j + 1));

}


return image;
}

/**
* Set the new color at row i and column j
*/
private void set(int[][] image, int i, int j, int newColor) {
image[i][j] = newColor;
}


/**
* @return Returns true if (i,j) inside the matrix and of the same old color.
*/
private boolean isInside(int[][] image, int i, int j, int oldColor) {
if (i > -1 && i < image.length && j > -1 && j < image[0].length && image[i][j] == oldColor)
return true;
else
return false;
}
}

class Pair {
int i;
int j;

public Pair(int i, int j) {
this.i = i;
this.j = j;
}
}


No comments:

Post a Comment