### 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 areauntil 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?

- This question, we simple change the color
**from A to B**. - 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));
}
}
```