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