algorithm - 更有效地找到差异较小的最大区域

Question

有一个由 h * w (h, w <= 200) 像素组成的网格，每个像素由一个值表示，我们要找到最大的连续区域。
一个连续区域是这样定义的:

1. Given a point P(x, y), The connected region must include this point.

2. There exists reference point R(x, y) of value v, any point in the connected region must be connected to this point. Also, there is a value g_critical(g_critical <= 100000). Let the value of a point in the connected region be v, the difference of u and v must be smaller or equal than g_critical.

问题是找到最大连接区域的大小。
例如网格。 h = 5, w = 5, g_critical = 3, P(x, y) = (2, 4)

1 3 7 9 2
2 5 6 6 8
3 5 9 3 6
2 7 3 2 9

在这种情况下，粗体区域是最大的连接区域。请注意，在这种情况下，在 (2, 3) 或 (2, 2) 处选择了 R(x, y)。该区域的大小为 14。
我已经改写了这个问题，所以它更短。因此，如果有任何歧义，请在评论中指出。这个问题也在我们的私有(private)法官中，所以我无法在这里分享问题来源。
我的尝试
我试图遍历每个单元格，将其视为 R 点并使用 bfs 来查找连接到它的连接区域。然后，检查 P 是否包含在该区域中。
复杂度为 O(h * h * w * w)，太大了。那么有什么办法可以优化呢？
我猜也许从 p 开始会有所帮助，但我不确定我应该怎么做。也许有某种洪水填充算法可以让我这样做？
提前致谢。

Answer 1

有一个 O(h w √(g_critical) α(h w)) 时间算法(其中 α 是反阿克曼函数，实际目的是常数)，它使用具有“撤消”操作和 Mo 技巧变体的不相交集数据结构.这个想法是，将区间 [v - g_critical, v] 分解为长度约为 √g_critical 的约 √g_critical 子区间。对于每个子区间 [a, b]，准备一个不相交的集合数据结构，表示矩阵的组件，其中允许的值为 [b, a + 2 g_critical]。然后对于 [a, b] 中的每个 c，用其值位于 [c, b) 和 (a + 2 g_critical, c + 2 g_critical] 的点扩展不相交集，并报告 P( x,y)，然后撤消这些操作(保留对结构所做的写入堆栈，带有原始值；然后弹出每个，写入原始值)。
还有一个你不会喜欢的 O(h w log(h w)) 时间算法，因为它使用动态树。 (Sleator–Tarjan 1985 年基于拉伸(stretch)树的构造是最简单的，并且在这里工作正常。)发布它主要是为了以防它激发更实用的方法。
高级思想是一种动力学算法，它在最多 g_critical + 1 个可能性上“滑动”允许值的间隔，重复报告并取最大值超过包含 P 的连接组件的大小。
为此，我们需要在派生图上维护最大生成森林。给定一个节点加权无向图，通过分割每条边并将每条新边的权重设置为它所关联的旧节点的权重，构造一个新的边权重图。删除图中最轻的节点很简单——如果可能，所有路径都会避开这些节点，因此新的最大生成森林将不再有任何边。要添加不在图中的最轻节点，请尝试一次链接它们的入射边。如果形成一个循环，则翻转一个端点，从另一个端点查询路径最小值，然后取消链接该最小值。
为了报告包含 P 的组件的大小，我们需要另一个修饰来捕获每个节点的具体子树(与表示的子树相反)的大小。细节有点粗糙。