python - 如何计算python数组中单独区域的数量

Question

我需要计算数组中单独区域的数量。

下面是一个示例数组。我可以计算唯一字符串的数量，但是如果在下面的网格中有两个不同的岛，如左上角和右下角的 64733，我的函数将无法正确计算区域数。如果两个区域由相同的数字组成，任何人都可以帮我找到一种计算区域数量的方法吗？我用 python 2.x 编写。

|64733|20996|92360|92360|04478|04478|04478|04478|04478|98101
|64733|92360|92360|92360|04478|04478|04478|04478|04478|04478
|64733|92360|29136|92360|04478|04478|04478|04478|04478|04478
|64733|92360|29136|92360|04478|04478|04478|04478|04478|04478
|92360|92360|92360|92360|04478|04478|04478|04478|04478|04478
|04478|04478|04478|04478|04478|04478|04478|04478|04478|04478
|04478|04478|04478|04478|04478|04478|04478|04478|04478|04478
|04478|04478|04478|04478|04478|04478|04478|04478|04478|04478
|04478|04478|04478|04478|04478|04478|04478|04478|04478|64773
|04478|04478|04478|04478|04478|04478|04478|04478|64773|64773

输入是一个 3d 数组，看起来像

[[['6', '4', '7', '3', '3'],
  ['2', '0', '9', '9', '6'],
  ['9', '2', '3', '6', '0'],
  ['9', '2', '3', '6', '0'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['9', '8', '1', '0', '1']],
 [['6', '4', '7', '3', '3'],
  ['9', '2', '3', '6', '0'],
  ['9', '2', '3', '6', '0'],
  ['9', '2', '3', '6', '0'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8'],
  ['0', '4', '4', '7', '8']],
 [['6', '4', '7', '3', '3'],
  ['9', '2', '3', '6', '0'],

这不是完整的输入（因为它很大），但我认为它很重要

因此，任何唯一的数字符号字符串所在的位置以及相同的相邻字符串的总数（相邻在左下右，而不是对角线）的位置也是如此。

enter code here

标签： python

Answer 1

你没有发布你的完整数组，所以我对你给我们的原始点分隔值做了一些假设。我已经在 Python 3 中编写了这个，但我认为它应该在 Python 2 中工作，只修改对语句的打印函数调用。

arr = [["64733","20996","92360","92360","04478","04478","04478","04478","04478","98101"],
["64733","92360","92360","92360","04478","04478","04478","04478","04478","04478"],
["64733","92360","29136","92360","04478","04478","04478","04478","04478","04478"],
["64733","92360","29136","92360","04478","04478","04478","04478","04478","04478"],
["92360","92360","92360","92360","04478","04478","04478","04478","04478","04478"],
["04478","04478","04478","04478","04478","04478","04478","04478","04478","04478"],
["04478","04478","04478","04478","04478","04478","04478","04478","04478","04478"],
["04478","04478","04478","04478","04478","04478","04478","04478","04478","04478"],
["04478","04478","04478","04478","04478","04478","04478","04478","04478","64773"],
["04478","04478","04478","04478","04478","04478","04478","04478","64773","64773"]]

x = len(arr)
y = len(arr[0])

#create a new array the same size as the original
regions = [[None for _ in range(y)] for _ in range(x)]

print(regions)

label = 0
queue = []

def check_neighbor(i, j, v):
    if not regions[i][j] and arr[i][j] == v:
        regions[i][j] = label
        queue.insert(0, (i, j))

for i in range(x):
    for j in range(y):
        #don't check an already labelled region
        if regions[i][j]: continue
        label += 1 #new label
        regions[i][j] = label
        queue = [(i, j)]
        v = arr[i][j]
        #keep checking neighbours until we run out
        while queue:
            (X, Y) = queue.pop()
            if X > 0:
                check_neighbor(X-1, Y, v)
            if X < x-1:
                check_neighbor(X+1, Y, v)
            if Y > 0:
                check_neighbor(X, Y-1, v)
            if Y < y-1:
                check_neighbor(X, Y+1, v)

print(regions)
print(label) # this is the number of regions