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

Question

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

下面是一个数组示例。我可以计算唯一字符串的数量，但是如果有两个不同的孤岛，比如在下面的网格中，64733位于左上角和右下角，我的函数将无法正确计算区域的数量。 如果两个区域由相同的数字组成，有谁能帮我找到一种计算区域数量的方法吗？我用python2.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数组，看起来像

^{pr2}$

这不是完整的输入（因为它是巨大的），但我认为它得到了要点

任何唯一的数字符号串和相同的相邻字符串的总数（相邻的是上下左右，不是对角线）也是如此。在

enter code here

Answer 1

你没有发布完整的数组，所以我对你给我们的原始pip分隔值做了一些假设。我已经用python3编写了这篇文章，但是我认为在python2中应该只修改对语句的print函数调用。在

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