在数组中查找封闭空间

Question

所以，我生成了一个空格数组，它们的属性是它们可以是红色或黑色。但是，我想防止红色被黑色包围。我有一些例子来说明我的意思：

0 0 0 0 0 0 0 1
0 1 0 0 0 0 1 0
1 0 1 0 0 0 0 1
0 1 0 0 1 1 1 0
0 0 0 0 1 0 1 0
1 1 1 0 1 1 1 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0

如果红色为 0，黑色为 1，则此示例包含四个外壳，我在生成数组时希望避免所有外壳。我的输入是数组的大小和我可以生成的 1 的数量。

我该怎么做呢？

Answer 1

问题实际上有两个部分。生成板子状态，然后检查是否正确。我意识到检查正确性实际上比仅仅确保始终生成正确的状态更糟糕。这就是我所做的：

请注意，我已将其定义self.WallSpaces为长度等于数组高度的数组，由位数等于数组宽度的整数组成。self.Width并self.Height提供数组的结束索引。基本上，Intersects它的工作原理是检查一个点周围的所有空间 1 秒，除了空间“构建”的方向（见下文），True如果其中任何一个是数组的边缘或 1，则返回。

def Intersects(self, point, direction):
    if (point[0] > 0):
        if (direction != [1, 0] and self.WallSpaces[point[0] - 1] & (1 << point[1]) != 0):
            return True
        if (point[1] == 0 or self.WallSpaces[point[0] - 1] & (1 << (point[1] - 1)) != 0):
            return True
        if (point[1] == self.Width or self.WallSpaces[point[0] - 1] & (1 << (point[1] + 1)) != 0):
            return True
    else:
        return True
    if (point[0] < self.Height):
        if (direction != [-1, 0] and self.WallSpaces[point[0] + 1] & (1 << point[1]) != 0):
            return True
        if (point[1] == 0 or self.WallSpaces[point[0] + 1] & (1 << (point[1] - 1)) != 0):
            return True
        if (point[1] == self.Width or self.WallSpaces[point[0] + 1] & (1 << (point[1] + 1)) != 0):
            return True
    else:
        return True
    if (point[1] == 0 or (direction != [0, 1] and self.WallSpaces[ point[0] ] & (1 << (point[1] - 1)) != 0)):
        return True
    if (point[1] == self.Width or (direction != [0, -1] and self.WallSpaces[ point[0] ] & (1 << (point[1] + 1)) != 0)):
        return True
    return False

方向GPacW.Left、GPacW.Right、GPackW.Up和GPacW.Down代表运动的基本方向。该函数的工作原理是从随机点在数组中构建“墙”，这些点可以向随机方向转动，并在它们相交两次时结束。

def BuildWalls(self):
    numWalls = 0
    directions = [ [GPacW.Left, GPacW.Right], [GPacW.Up, GPacW.Down] ]
    start = [ random.randint(0, self.Height), random.randint(0, self.Width) ]
    length = 0
    horizontalOrVertical = random.randint(0, 1)
    direction = random.randint(0, 1)
    d = directions[horizontalOrVertical][direction]
    intersected = False
    while (numWalls < self.Walls):
        while (start == [0, 0] or start == [self.Height, self.Width] or self.Intersects(start, d)):
            start = [ random.randint(0, self.Height), random.randint(0, self.Width) ]
        if (length == 0):
            horizontalOrVertical = not horizontalOrVertical
            direction = random.randint(0, 1)
            length = random.randint(3, min(self.Height, self.Width))
            d = directions[horizontalOrVertical][direction]
        if (self.WallSpaces[ start[0] ] & (1 << start[1] ) == 0):
            self.WallSpaces[ start[0] ] |= 1 << start[1]
            numWalls += 1
            length -= 1
        if (0 <= (start[0] + d[0]) <= self.Height and 0 <= (start[1] + d[1]) <= self.Width):
            start[0] += d[0]
            start[1] += d[1]
        else:
            start = [0,0]
        if (self.Intersects(start, d)):
            if (intersected):
                intersected = False
                start = [0,0]
                length = 0
            else:
                intersected = True
    return