我有矩阵：
5 5 1 4 4
4 0 2 4 2
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
正如你所看到的，矩阵中有带零的区域。对于类似零的楼梯区域(查看坐标(1, 1)(2, 1)(2, 2)。这是由包围的
- 具有数字
1的0区域 - 数字为
2的1区域 - 具有数字
3的1区域 - 数字为
4的2区域 - 数字为
5的2区域
要点是，如果相邻元素具有相同的值，则数字区域可以是连续的。
例如，查看坐标(0, 1)上离零区域最近的5。它具有坐标为(0, 0)的邻居。此外，从(2, 0)坐标放置的第二5区域具有邻居(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上的所有零都被替换。其他零区域也是如此。
问题是我应该使用什么算法我想到的唯一想法是创建一些巨大的地图字典，并以某种方式查找坐标的交点并改变状态，但这是错误的。我不知道该怎么解决这个问题了！
我的方法
- 首先，使用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的复杂性+零区域的大小=O(M(，其中M是矩阵中的元素数=O(N^2(，其中N是矩阵的行和列