Cracking Coding Interview - 8.10 Paint Fill

Paint Fill: 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.

Hints: #364, #382

解法1

举个例子:如果一个画布背景是白色,上面有一个黑色的方块,点中这个方块中的某个坐标,把这个方块变成绿色。

如果两个方块顶点相碰,那么只会有一个方块变颜色。这也就是体重所说的surrounding区域变色,而surrounding的概念则是上下左右4个方向,不含斜方向。要注意避免重复着色。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public void paintFill(byte[][] screen, int r, int c, byte toColor) {
  byte srcColor = screen[r][c];
  paintFill(screen, r, c, srcColor, toColor);
}

public void paintFill(byte[][] screen, int r, int c, byte srcColor, byte toColor) {
  if (r < 0 || c < 0 || r >= screen.length || c >= screen[0].length) {
    // 越过屏幕边界
    return;
  }
  byte meColor = screen[r][c];
  if (meColor != srcColor) {
    return;
  } 
  screen[x][y] = toColor;
  paintFill(screen, r + 1, y, srcColor, toColor); // up
  paintFill(screen, r - 1, y, srcColor, toColor); // down
  paintFill(screen, x, c + 1, srcColor, toColor); // right
  paintFill(screen, x, c - 1, srcColor, toColor); // left
}

版权

评论