算法 - 查找连接的图块组

Question

我非常抱歉这个头衔,但用几句话描述我的问题有点难.我认为帖子的其余部分会更好地解释它!;)

描述

我基本上有一个瓷砖/对象/符号的二维数组,每当一组瓷砖被特殊瓷砖分隔时,我想把它分成两个(或更多)新的二维数组.

例如,如果我有:

[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]

每组互连瓦片的一个阵列.

在我的特定情况下,我将null对象作为x,并将其余对象作为任意对象.基本上,如果我不能从瓦片A到达瓦片B而没有穿过零,那么这两个是两个不同的组.

我已经在脑海里玩了一段时间了,我能想到的最好的肯定比O(n ^ 2)差得多,因为它们甚至在第一时间工作.洪水填充会让人想起可以用来查找组的东西,但除此之外,我不确定我是否可以在此实例中提出任何其他类似的问题.

这个问题

所以我要问的是,你是否碰巧知道在哪个方向上解决我的问题和/或如何解决它.计算复杂性并不是那么重要,因为我计划不经常执行此操作,也不会在大型数组上执行.不过,我希望我没有遇到NP难题!:3

谢谢!

Answer 1

我希望我没有遇到NP难题!

这远非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

我希望这有帮助.

因为你不关心它,所以我没有理会显示复杂性.