问题标签 [flood-fill]

我需要检查我的游戏角色可以到达的网格的所有单元格。为此，我需要从字符位置开始，然后“淹没”该区域以找到所有可到达的单元格（例如，未被墙壁阻挡的单元格）。

在此图中，玩家是P，阻挡玩家的墙壁由 表示X。我需要检查玩家所在区域的所有单元格。

有没有很好的迭代算法来做到这一点？目前我正在递归地执行此操作。

我想在我的 iphone 应用程序中实现洪水填充算法。我一直在搜索很长一段时间，我已经看到了所有堆栈溢出的答案，但没有任何帮助。

请任何人发布一些使用洪水填充的示例应用程序代码。

所以递归不是我的强项，我一直面临挑战，要创建一个递归的 floodFill 函数，如果值为零，则用 1 填充整数向量的向量。由于我以外的原因，我的代码不断出现段错误。也许我的代码会让这听起来更清楚。

这是要填充的网格：

它属于我创建的一个名为“Grid”的对象，它基本上是一组帮助操作向量的函数。网格的值被初始化为全零。

这是我的洪水填充功能：

这里的目的是让函数检查一个点的值是否为零，如果是，则将其更改为 1。然后它应该检查它上面的那个。它会这样做，直到找到 1 或到达向量的末尾。然后它尝试另一个方向并继续前进，直到与上述相同的条件，依此类推，直到洪水充满。

谁能帮我解决这个问题？也许告诉我怎么了？

谢谢！

我正在为一组几个场地开发一个预订可用性系统，并且很难生成给定月份中几天的时间块可用性。这发生在 PHP 的服务器端，但这个概念本身与语言无关——我可以在 JS 或其他任何东西中这样做。

给定一个venue_id、月份和年份（例如6/2012），我有一个在该地点范围内发生的所有事件的列表，表示为unix时间戳start和end. 该数据来自数据库。我需要确定每天存在什么（如果有）最短长度的连续时间段（每个场地不同）。

例如，在 6 月 1 日下午 2:00 到 7:00 之间我有一个活动。最短时间为 5 小时，因此上午 9 点至下午 2 点和晚上 7 点至 12 点之间有一个街区开放。这将在六月的每一天持续到第二、第三等等。有些（大多数）日子根本没有发生任何事情，有些日子有 1 - 3 个事件。

我想出的解决方案有效，但生成数据也需要很长时间。基本上，我在每个月的每一天循环，并为当天的每 15 分钟创建一组时间戳。然后，我将当天事件的时间跨度循环 15 分钟，将任何“已采取”时间段标记为错误。剩下的，我有一个数组，其中包含空闲时间与所用时间的时间戳：

现在我需要循环这个数组来找到连续的时间块，然后检查它们是否足够长（每个场地都有一个最小值），如果是，那么为它们的开始和结束建立描述性文本（即上午 9 点 - 下午 2 点） . 哇！当所有这些循环完成时，用户已经厌倦了，并徘徊在 Youtube 上观看小狗的视频；这样检查需要很长时间，大约需要 30 天。

有没有更快的方法来解决这个问题？总结这个问题，给定 d 天的时间范围t1和t2，我如何确定d中剩余的剩余时间比最小时间块m长。

当用户在日历月之间移动时，这些数据通过 AJAX 按需组装。结果是按页面加载缓存的，因此如果用户第二次进入 7 月，第一次生成的数据将被重用。

任何其他有帮助的细节，请告诉我。

编辑

根据请求，数据库结构（或此处相关的部分）

事件总是在 15 日开始 -- :00, :15, :30, :45

一些实际时间戳的数据转储：http: //pastebin.com/k1PRkj44

我在运行以下代码时遇到了无限循环。在一个被块包围的网格内，一个预定义的正方形开始于此实现运行。如果需要访问一个正方形，则将其标记为 1，如果已访问，则将其标记为 2。我似乎找不到解决方案，我希望得到一些有用的提示。

我的洪水填充功能无法正常工作时遇到了一些问题。此分配的目的是查看 P 和 C 在数组内是否连接。在洪水填充功能中，它似乎没有将“_”更改为“P”

样本输入

代码

我在某处有内存泄漏。我已经搜索了很多次，对我来说它看起来很可靠。我只是.. 找不到... 找到它... 好的，背景。这是一个堆栈驱动的洪水填充，这段代码是我向堆栈添加东西的唯一地方。代码比较多，如果没有人发现内存泄漏，我会再贴一些。

这是关于这个的最奇怪的部分。该代码仅适用于一种颜色+线条艺术（图片纹理），但是当使用多种颜色并使用填充桶时，我会遇到那些奇怪的内存泄漏。

编辑：我刚刚意识到我忘了提到最奇怪的部分。在我使用起始颜色（蓝色）以外的颜色之前，这段代码工作得很好。一旦我改变颜色，即使它变回蓝色，它仍然会破裂。

Flood-fill算法的通用实现遇到堆栈溢出，有什么办法可以优化吗？我正在使用此算法在建筑模型中找到不同的空隙区域。我对这些模型进行体素化，然后解析通过简化版本的 0 和 1 表示的体素化结果。0 和 1 表示体素是否存在。0 存在，1 不存在。然后我必须找到连接 0 的不同子集，换句话说，就是 3D 建筑物内的连接空隙空间。

示例 2D 输入数据示例存储在列表中，3D 将是列表中的多个条目。(Z, Y, X) = (0, 4, 9)

维基百科提出了几种补救措施，但我不知道如何实施。这是现有的算法，我已经为更密集的数据设置了“sys.setrecursionlimit(10000)”。这对某些人来说很好，但对于更密集的 (Z, Y, X) = (50, 46, 22) 或更大，因为建筑模型变得更加复杂，有数百个房间，我收到堆栈溢出消息

递归函数会发生错误堆栈溢出：

代码：

我正在尝试创建一个填充方法，该方法采用用户指定的初始坐标，检查字符，然后根据需要更改它。这样做之后，它会检查相邻的方格并重复该过程。经过一番研究，我遇到了洪水填充算法，并在尝试之后（它可以工作，但不能满足我对 250 x 250 个字符的数组的最大要求）。

我原来的洪水填充算法如下：

测试后，我开始尝试 Queue 方法，如Wikipedia上解释的那样，这个问题之前就类似的问题提出过。到目前为止，我已经想出了以下代码：

虽然第一种递归方法能够处理较小的值，但当数组变得太大时它就不起作用了。但是，第二种方法将我带入某种无限循环，由于我对队列缺乏经验，我无法识别这种循环。如何优化第一个代码示例以处理更大的示例或修复第二个代码示例以提供结果？谁能解释如何编写这两者中的任何一个或我做错了什么？

谢谢！

编辑：我能够在第二个代码中找到无限循环错误（已修复），但基于队列的方法没有填满整个区域。事实上，它比基于递归的方法填充的区域更少。编辑 2：它现在适用于方形数组。如何确保它也适用于矩形阵列（第二种方法）。

给定图像上的一个点，我想填充连接到该点的所有点 - 但到一个新图像上。一种天真的方法是将原始图像填充为特殊的魔法颜色值。然后，访问每个像素，并将所有具有此神奇颜色值的像素复制到新图像中。一定会有更好的办法！