java - paintFill 函数的实现

Question

我对下面来自 McDowell 的实现 paintFill 函数(类似于图像编辑程序)的代码有几个问题。

1- 为什么我们使用排序 screen[y][x] 而不是 screen[x][y]？作者说这是图形问题的特点，但为什么呢？

2- 作者将这种方法与深度优先方法进行了比较，并表示它可能会很快溢出堆栈。另一种方法是实现广度优先搜索的变体。它不是已经是 bfs 方法了吗？因为对于每个像素，我们先给相邻像素着色，然后再向外看？如果不是，bfs 方法的想法是什么，为什么它也不会溢出？

  enum Color{
    Black, White, Red, Yellow, Green
  }

  boolean paintFill(Color[][] screen, int x, int y, Color ocolor, Color ncolor){
    if (x < 0 || x >= screen[0].length||
            y < 0 || y >= screen.length){
      return false;
    }

    if (screen[y][x] == ocolor){
      screen[y][x] = ncolor;
      paintFill(screen, x-1, y, ocolor, ncolor);
      paintFill(screen, x+1, y, ocolor, ncolor);
      paintFill(screen, x, y-1, ocolor, ncolor);
      paintFill(screen, x, y+1, ocolor, ncolor);
    }
    return true;
  }

  boolean paintFill(Color[][] screen, int x, int y, Color ncolor){
    if (screen[y][x] == ncolor){
      return false;
    }
    return paintFill(screen, x, y, screen[y][x], ncolor);
  }

Answer 1

1. 图像格式和屏幕设备使用水平扫描线，因此是水平线的垂直阵列。所以 [y][x]。查看模拟电视信号，BMP 格式。

2. DFS 的可视化将是雷击，而 BFS 将在培养皿中培养细菌菌落。由于任何搜索都不是定向的，因此 DFS 有许多部分候选路径，它们向任何方向 curl ，因此更长。 BFS 更自然。就像您要保持生长的外部轮廓一样。另一种观点是:BFS 的增长受到外边界的限制，而 DFS 以不受限制的 curl 路径开始。这些路径更长，效率可能呈指数级下降。最大路径长度 B*W 将是递归深度。在 C 中，可以定义一个小堆栈，但堆栈溢出似乎有点过头了。