在python中计算2d数组中相邻相等元素的数量

Question

我正在尝试在2D数组中查找许多相邻元素。当我说相邻时，我指的是水平和垂直。

例如：

[[1, 2, 1, 3],
 [2, 1, 3, 1],
 [3, 2, 3, 1],
 [2, 3, 2, 1]]

这个数组的结果将是5，因为一直向右的三个1+中间的两个3彼此相邻。假设给定的2d阵列可以比我在这里给出的例子更大，那么实现这一点最不耗时的方法是什么？

谢谢。

Answer 1

这个问题类似于流行的计算岛屿数量的问题。通常，计数岛问题表示为0和1的矩阵。例如

[
[0 1 0],
[1 1 0],
[0 1 0],
]

因此，从那里开始，你可以做一个BFS来计算相似(相等(的相邻数，而不是1。

以下只是问题的简化

A = [[]]
visited = [[]] // matrix of booleans, contains the already visited i,j
for i in range(1, len(mat)):
    for j in range(1, len(mat[i])):
       BFS(A[i][j], A, i, j, visited)

然后，

func BFS(target, matrix, i, j, visited):
   // do the normal island count logic, but using "target" instead of 1s

参考。

https://leetcode.com/problems/number-of-islands/

https://www.techiedelight.com/count-the-number-of-islands/