算法 - 查找连接瓦片的群组

Question

算法 - 查找连接瓦片的群组

arraysalgorithmmultidimensional-array

3

我非常抱歉标题不太恰当，但用几个词来描述我的问题有点困难。我想其余的帖子会更好地解释它！;)

描述

我基本上有一个二维数组，包含瓷砖/对象/符号，我想在特殊瓷砖分隔一组瓷砖时将其拆分成两个（或更多）新的二维数组。

例如，如果我有：

[x][x] [0] [0]

[0] [0] [x] [0]

[0] [0] [0] [x]

其中符号 x 不需要，则应该给我两个新数组：

[x] [x] [0] [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作为null对象，其他任意对象。基本上，如果我不能从瓷砖A到达瓷砖B而不穿过空值，则这两个瓷砖是两个不同的组。

我在脑海中考虑了一段时间，最好的解决方法肯定比O(n^2)差得多，即使它们在第一次使用时有效。Flood fill似乎可以用来找到一个组，但除此之外，我不确定我能想出任何其他类似的问题来解决这个问题。

问题

所以我问的是，如果你恰好知道解决我的问题的方向和/或如何解决它。计算复杂度并不是非常重要，因为我计划不经常执行此操作，也不会在大数组上执行。尽管如此，我希望我没有碰到NP-hard问题！：3

谢谢！

- Robert Kaufmann

"并查集" 可能是一个解决方案。 - wildplasser

2个回答

3

看起来你需要使用连通组件标记算法来分离物体的不同组。

- MBo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alexander · Accepted Answer

我希望这不是一个NP难题！

这远非NP问题。

我将解释两种不同的方法来解决这个问题。一种将使用Flood Fill，正如您所期望的那样，另一种将使用Disjoint-set数据结构。

Flood Fill

假设您有一个矩阵N x M，其中位置(row, column)为null时未使用，否则它包含一个值。

您需要遍历每行1..N的每个列元素1..M。这很简单：

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

你可以修改这个算法，如果你跟踪识别的区域数量，可以在不同的数组中标记每个区域的指定编号。你会注意到我使用了队列而不是递归函数，这将使你远离达到最大递归限制。

并查集算法

另一种解决方案是使用不相交集数据结构来实现相同的目的。我只会展示对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

我希望这能帮到你。

我没有介意展示复杂性，因为你不关心它。