Question

Implement the “paint fill” function that one might see on many image editing programs.

That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.

Solution

This is a BFS/DFS question, very similar to [LeetCode 130] Surrounded Regions.

However, this question is not same as surrounding region, because no temporary storage of state is needed, and we DO NOT NEED TO keep track of the visited positions!

Why is this?

  1. This question, we simple change the color from A to B.
  2. Surrounding Region is change A to B, and B to A.

That’s why, the nature of 2 questions are different.

Code 1 is my first solution, and Code 2 is doing a BFS and set color directly to expected value. This type of questions is highly frequent and sometimes may cause confusions.

Code

my code 1, with ‘temp’ state

public static void PaintFill1(Color[][] screen, int posX, int posY,
        Color ncolor) {
    // the queue keeps the list of positions that I'm going to visit
    Queue<Position> q = new LinkedList<Position>();
    int len = screen.length;
    Color original = screen[posX][posY];
    // visited origin node first
    q.offer(new Position(posX, posY));
    while (!q.isEmpty()) {
        // visit positions in q one by one (mark color as 'Temp')
        Position p = q.poll();
        if (p.x < 0 || p.x >= len || p.y < 0 || p.y >= len) {
            // invalid pos coordinate
            continue;
        } else if (screen[p.x][p.y] == Color.Temp
                || screen[p.x][p.y] != original) {
            continue;
        }
        screen[p.x][p.y] = Color.Temp;
        q.offer(new Position(p.x - 1, p.y));
        q.offer(new Position(p.x + 1, p.y));
        q.offer(new Position(p.x, p.y - 1));
        q.offer(new Position(p.x, p.y + 1));
    }
    // finish visiting all positions that's original color
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (screen[i][j] == Color.Temp) {
                screen[i][j] = ncolor;
            }
        }
    }
}

my code 2, without ‘temp’ state

public static void PaintFill2(Color[][] screen, int posX, int posY,
        Color ncolor) {
    // the queue keeps the list of positions that I'm going to visit
    Queue<Position> q = new LinkedList<Position>();
    int len = screen.length;
    Color original = screen[posX][posY];
    // visited origin node first
    q.offer(new Position(posX, posY));
    while (!q.isEmpty()) {
        // visit positions in q one by one (mark color as 'Temp')
        Position p = q.poll();
        if (p.x < 0 || p.x >= len || p.y < 0 || p.y >= len) {
            // invalid pos coordinate
            continue;
        } else if (screen[p.x][p.y] != original) {
            continue;
        }
        screen[p.x][p.y] = ncolor;
        q.offer(new Position(p.x - 1, p.y));
        q.offer(new Position(p.x + 1, p.y));
        q.offer(new Position(p.x, p.y - 1));
        q.offer(new Position(p.x, p.y + 1));
    }
}