Skip to content

Instantly share code, notes, and snippets.

@OmarMalik
Created April 30, 2019 15:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save OmarMalik/37b8841aa24a1e7d56cbdcea27c97c68 to your computer and use it in GitHub Desktop.
Save OmarMalik/37b8841aa24a1e7d56cbdcea27c97c68 to your computer and use it in GitHub Desktop.
omar's flood fill
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
boolean[][] visited = new boolean[image.length][image[0].length];
Queue<Point> q = new ArrayDeque<Point>();
q.add(new Point(sr, sc));
visited[sr][sc] = true;
while (!q.isEmpty()) {
Point curr = q.remove();
int r = curr.r;
int c = curr.c;
if (inBounds(image, r + 1, c) && !visited[r + 1][c] && image[r][c] == image[r + 1][c]) {
q.add(new Point(r + 1, c));
visited[r + 1][c] = true;
}
if (inBounds(image, r, c + 1) && !visited[r][c + 1] && image[r][c] == image[r][c + 1]) {
q.add(new Point(r, c + 1));
visited[r][c + 1] = true;
}
if (inBounds(image, r - 1, c) && !visited[r - 1][c] && image[r][c] == image[r - 1][c]) {
q.add(new Point(r - 1, c));
visited[r - 1][c] = true;
}
if (inBounds(image, r, c - 1) && !visited[r][c - 1] && image[r][c] == image[r][c - 1]) {
q.add(new Point(r, c - 1));
visited[r][c - 1] = true;
}
image[r][c] = newColor;
}
return image;
}
public boolean inBounds(int[][] image, int r, int c) {
return r < image.length && c < image[0].length && r >= 0 && c >= 0 ;
}
class Point {
int r, c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment