3

我正在尝试实现简单的边界填充方法（使用 4 个连接的方法）来填充矩形。我是按如下方式进行的（下面的代码），但是矩形没有被正确填充：当它到达矩形的一半时它停止填充。

但是在尝试填充圆圈时，相同的代码可以正常工作。谁能帮我找出问题所在？

提前致谢

#include <stdio.h>
#include <conio.h>
#include <graphics.h>

void boundfill(int xc, int yc, int r, int b) {
    int cur;
    cur = getpixel(xc, yc);
    if (cur != b && cur != r) {
        putpixel(xc, yc, r);
        delay(1);

        boundfill(xc + 1, yc, r, b);
        boundfill(xc - 1, yc, r, b);
        boundfill(xc, yc + 1, r, b);
        boundfill(xc, yc - 1, r, b);
    }
}

void main() {
    int gd = DETECT, gm;
    initgraph(&gd, &gm, "..\\bgi");

    rectangle(100, 100, 300, 300);
    boundfill(105, 105, 4, WHITE);

    getch();
    closegraph();
}

输出：

输出 1

但是当我对矩形使用以下坐标时，它工作正常。给定坐标：

rectangle(50, 50, 100 ,100);
boundfill(55, 55, 4, WHITE);

为此，输出为：

输出 2

4

2 回答 2

0

你用的是什么平台？

  • 这是 32 位还是 16 位可执行文件？

BGI 是非常古老的 Borland gfx API，仍然用于学习目的，如果它是原始的 Borland BGI，那么您正在创建 16 位 DOS 应用程序。在这种情况下，还有适用于 Windows 和 Linux 的 BGI 包装器/模拟器，这取决于您的编译器设置。

什么可能是错的：

  1. 堆/栈

    在 16 位 DOS 模式下，您只能看到前 1 MB 的内存空间，其中 640 KB 可用于整个系统。在您的程序/项目/编译器设置中，还有其他约束，例如您的应用程序的初始/最大堆和堆栈大小。如果设置得太低，那么你可能会遇到堆堆栈问题，在这种情况下它应该抛出异常，但根据我的经验，我看到很多奇怪的东西然后丢失了异常。

    当您填充 100x100 像素区域时，您将递归多达 10000 次，并且您的递归调用（16 位案例）包含：

    1 x return address segment+offset = 4 Byte
4 x int16 operand = 8 Byte
1 x int local variable = 2 Byte

    总共 14 字节（在某些 C/C++ 引擎上被截断为 16 字节）不包括像 putpixel 这样的子调用需要的额外数据......将它乘以递归计数，您在 16 位 DOS 上肯定远高于安全性。要检查这一点：

    • 每次填充都应该在同一个位置停止（如果您的代码中没有更多处理）
    • 如果你在函数头中添加一些变量，它应该比之前更早停止
    • 堆/堆栈限制的变化也应该影响这一点

    修复这个从递归中消除所有不必要的东西，例如b,r是恒定的，所以它们可以在全局变量中。如果您xc,yc在返回之前设置回原始状态，则可以使用&xc,&yc. 您的 cur 局部变量可以是静态的。这将消除递归中的所有分配，仅保留返回地址。

  2. gfx 模式

    BGI 主要用于 16 种颜色模式，分辨率更高，您正在跨越 64KB 的障碍。如果您的 BGI 驱动程序有问题，它可能会挂起或停止绘图。在这种情况下，无论子弹#1是什么，都会在同一个地方停止。为避免此更改 BGI 驱动程序，请使用不同的分辨率或更好的模拟器

于 2014-09-29T08:01:30.597 回答
0

没有其他信息 - 这闻起来就像堆栈溢出。我的假设基于以下几点：

  1. 您的算法过于递归。
  2. 更大的矩形出现问题
  3. 您提供的填充模式与您的程序刚刚初步“停止”（实际上崩溃）的假设一致。也就是说，您的递归路径首先水平填充，然后垂直填充。

撇开对这种特定填充算法的有效性的讨论，请注意，通常只有在递归深度具有合理限制时才可以使用递归算法。

例如，在平衡二叉树上使用递归是可以的，因为这样的树深度（以及递归深度）随着树的大小呈对数增长。另一方面，使用递归进行链表操作是不合理的。

如果你坚持使用这个特定的算法，我相信你应该摆脱递归。您可以将起点放入队列中，然后在循环中从队列中弹出一个点，绘制并将其邻居推入队列。类似于 BFS 算法。

于 2016-11-28T08:08:16.727 回答