3

我想知道如何在数组上应用洪水填充，我的数组是二维的，其中包含新的罗马字体类型字母边界。边界线包含 1 和内部和外部全 0。我想只在里面填写所有 1 而不是 0。但我需要一个不需要更多内存的逻辑。所以避免递归和堆栈或队列

4

4 回答 4

4

我通常不为其他人做作业，但我喜欢这个挑战：

int c = -1;
while (c < 0)
{    
    /* Store breadcrumb trail, look to carry on */
    a[x][y] = c--;
    if (!hunt(0))
    {
        /* Nowhere to go, so back-track by looking for breadcrumb */
        a[x][y] = 1;
        c += 2;
        hunt(c);
    }
}

bool_t hunt(int v)
{
    if (a[x-1][y] == v)  { x--; return TRUE; }
    if (a[x+1][y] == v)  { x++; return TRUE; }
    if (a[x][y-1] == v)  { y--; return TRUE; }
    if (a[x][y+1] == v)  { y++; return TRUE; }
    return FALSE;
}

请注意，这不会检查是否击中数组的边缘。此外，它假设您的数组元素是例如ints，并且您只使用图像中的值0和1。

于 2010-10-23T09:02:09.343 回答
1

你的任务没有多大意义。如果你有一个字体，你不想用泛色填充来填充它，而是直接将它渲染为填充多边形。确定哪些部分进出字体，特别是对于衬线字体，如果不能可靠地给出好的结果。

填充多边形的典型示意图算法是这样的（不需要堆栈或递归），它也可以在某些条件下应用于位图（我会谈到）：

对于每条线（或列，更适合您的数据结构），在您跟随的虚拟线和所有多边形线（边界）的每个交点处切换填充。

假设这个（可能是 O 字符的中间线）：

00010010001001000
   ^  ^   ^  ^
   |  |   |  stop
   |  |   start
   |  stop
   start

结果：

00011110001111000

这也适用于位图，但前提是您实际上总是有两个边界用于开始和停止。

于 2010-10-23T09:27:54.320 回答
0 
function LowMemFloodFill(pixel)
  FillPixel(pixel)
  Do
    didFill = false
    For each pixel
      If current pixel has been filled
        For each adjacent pixel
          If adjacent has not been filled
            FillPixel(adjacent)
            didFill = true
          End
        End
      End
    End
  While didFill
End

问题是您必须能够判断像素已被填充（用未使用的颜色填充）。此外，这将非常缓慢。

于 2011-02-06T01:20:43.763 回答
-1

你基本上不能。您必须将这些信息存储在某处，因为在完成当前部分后，您必须知道从哪里开始填写。递归可以让你隐式地做到这一点。保留自己的堆栈可以让您明确地做到这一点，可能会节省一些。Oli Charlesworth 通过保持与图片大小相同的数组做了一件可爱的事情，但这比递归或保持堆栈位置使用更多的内存。

于 2010-10-23T09:18:30.553 回答