如何探索矩阵中零元素的最大可能连续长度的相邻区域？

Question

我有矩阵：

如您所见，矩阵中有带零的区域。对于阶梯状的零区域（看坐标(1, 1)(2, 1)(2, 2)。这是被

包围的

0 个数字为 1
1 个数字为 2
1 个数字为 3
2 个数字为 4
2 个数字为 5

重点是如果相邻元素具有相同的值，则数字区域可以连续。

例如，在坐标 (0, 1) 上查看离零区域最近的 5。它有坐标为 (0, 0) 的邻居。此外，第二个 5 区域位于 (2, 0) 坐标附近，具有邻居 (3, 0)。所以，总的来说，我们有两个坐标为 (0, 1), (0, 0), (2, 0), (3, 0) 的 5 区域，因此这个零区域的 5 区域的长度是4!

3 的长度为 3（它从 (3, 2) 开始到 (4, 2) 然后到 (4, 1)。重点是在 1, 2, 3, 4, 5 范围内的值上替换零区域的元素（即其中的所有零），其中相应的数字区域具有最大长度。在我们的例子中，所有零都被替换为 5。同样的事情是与其他零区域。

问题是我应该使用什么算法？我想到的唯一想法是创建一些巨大的地图字典并以某种方式查找坐标的交叉点并更改状态，但这是错误的。我不知道如何解决这个问题！

Answer 1

我的做法

首先，使用DFS或BFS来识别具有相同数字的连续区域。这可以通过
- 访问每个单元格（以任何顺序，例如从上到下，从左到右）
- 如果访问过的单元格没有被标记为属于已知的连续区域，运行DFS或BFS从该单元格开始并连接到具有数字的相邻单元格，然后标记所有访问过的单元格DFS/BFS作为一个新领域
- 如果访问过的单元格已被标记，则继续下一个单元格
完成所有 DFS/BFS 后，您将获得从每个单元格到每个独特区域的地图。比如下面这样划分区域（为了避免和数字混淆，我会用字母来标示区域，但实际上你也可以用整数来标示区域）

a a b c c
d e f g h
i e e j k
i l m n o
p m m q o

您还应该计算每个区域的长度：area_len = {a: 2, b: 1, c: 2, etc...}，以及与 0 关联的区域集：zero_areas = {e, k, n}
接下来，您需要构建与每个数字相关联的零点相邻区域集：D[i] = set of neighour of zeros associated with digits i。例如，D[5] = {a, i}, D[1] = {o}。
- 这可以通过遍历零区域中的所有单元格并查看这些单元格的所有邻居来完成

for area in zero_areas:
   for cell in area:
      for neighbour_cell in neighbours of cell:
          add area of neighbour_cell to D[digit of neighbour_cell]

最后，对每个数字i，计算D[i]中的面积长度之和，选择最大的

时间复杂度 = DFS/BFS 的复杂度 + zero-areas 的大小 = O(M)，其中 M 是矩阵中元素的数量 = O(N^2)，其中 N 是行和矩阵的列

如何探索矩阵中零元素的最大可能连续长度的相邻区域？

How to explore adjacent areas with maximal possible continuous length for the zero-element in matrix?

algorithm

matrix

dynamic-programming

greedy