我对标题感到非常抱歉，但是用几个词来描述我的问题有点困难。我想这篇文章的其余部分会更好地解释它! ;)
说明
我基本上有一个瓦片/对象/符号的二维数组，每当一组瓦片被特殊瓦片分隔时，我想将它分成两个(或更多)新的二维数组。
例如，如果我有:
[x][x] [0][0]
[0][0] [x] [0]
[0][0] [x] [0]
[0][0][0] [x]
在不需要符号 x 的地方，那应该给我两个新数组:
[x][x] [0][0]
[x][x][x] [0]
[x][x][x] [0]
[x][x][x][x]
和
[x][x][x][x]
[0][0] [x][x]
[0][0] [x][x]
[0][0][0] [x]
每组互连瓦片一个阵列。
在我的特定情况下，我有空对象作为 x，其余的有一个任意对象。基本上，如果我不能在不跨越空值的情况下从图块 A 到达图块 B，那么这两个是两个不同的组。
我已经在脑子里玩了一段时间，我能想出的最好的肯定比 O(n^2) 差得多，因为它们甚至首先工作。 Flood fill 让人想起可以用来查找组的东西，但除此之外，我不确定我能想出任何其他类似的问题来在这种情况下使用。
问题
所以我要问的是，您是否碰巧知道解决我的问题的方向和/或如何解决它。计算复杂度并不是那么重要，因为我不打算经常执行此操作，也不打算在大型数组上执行此操作。不过，我希望我没有遇到 NP 难题! :3
谢谢!
最佳答案
这远不是一个NP问题。
我将解释两种不同的方法来解决这个问题。一个将按照您的预期使用 Flood Fill ，另一个将使用 Disjoint-set 数据结构。
洪水填充
假设您有一个矩阵 N x M，其中 (row, column) 的位置在未使用时为 null，否则它包含一个值。
您需要遍历每行 1..M 的每个列元素 1..N 。这很简单:
for row in range(1, N + 1):
for column in range(1, M + 1):
if matrix[row][column] is not null:
floodfill(matrix, row, column)
每次发现非
null值都需要调用Flood Fill算法，后面我会定义Flood Fill方法，原因就更清楚了。def floodfill(matrix, row, column):
# I will use a queue to keep record of the positions we are gonna traverse.
# Each element in the queue is a coordinate position (row,column) of an element
# of the matrix.
Q = Queue()
# A container for the up, down, left and right directions.
dirs = { (-1, 0), (1, 0), (0, -1), (0, 1) }
# Now we will add our initial position to the queue.
Q.push( (row, column) )
# And we will mark the element as null. You will definitely need to
# use a boolean matrix to mark visited elements. In this case I will simply
# mark them as null.
matrix[row][column] = null
# Go through each element in the queue, while there are still elements to visit.
while Q is not empty:
# Pop the next element to visit from the queue.
# Remember this is a (row, column) position.
(r, c) = Q.pop()
# Add the element to the output region.
region.add( (r, c) )
# Check for non-visited position adjacent to this (r,c) position.
# These are:
# (r + 1, c): down
# (r - 1, c): up
# (r, c - 1): left
# (r, c + 1): right
for (dr, dc) in dirs:
# Check if this adjacent position is not null and keep it between
# the matrix size.
if matrix[r + dr][c + dc] is not null
and r + dr <= rows(matrix)
and c + dc <= colums(matrix):
# Then add the position to the queue to be visited later
Q.push(r + dr, c + dc)
# And mark this position as visited.
matrix[r + dr][c + dc] = null
# When there are no more positions to visit. You can return the
# region visited.
return region
如果您跟踪识别的区域数量，您可以修改此算法以在不同的数组中用指定的数字标记每个区域。您会注意到我使用的是队列而不是递归函数，这将使您远离达到最大递归边界限制。
联合查找算法
我认为更昂贵的另一个解决方案是使用 Disjoint-set 数据结构来实现相同的目的。我只会展示对
floodfill 方法的更改。def floodfill(matrix):
disjoint_set = DisjointSet()
# Go through each row in the matrix
for row in range(1, N + 1):
# Go through each column in the matrix
for column in range(1, M + 1):
# Create a set for the current position
disjoint_set.makeSet(row, column)
if matrix[row - 1][column] is not null:
# If the position north of it it is not null then merge them
disjoint_set.merge((row, column), (row - 1, column))
if matrix[row][column - 1] is not null:
# If the position left of it it is not null then merge them
disjoint_set.merge((row, column), (row, column - 1))
# You can go through each position identifying its set and do something with it
for row in range(1, N + 1):
for column in range(1, M + 1):
regions[ disjoint_set.find(row, column) ] = (row, column)
return regions
我希望这会有所帮助。
我没有费心展示复杂性，因为你并不关心它。
关于arrays - 算法 - 查找连接的瓷砖组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10667497/