在二维数组中查找封闭空间

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的数量。如何解决这个问题？

- Woody1193

---

对于每个“0”空间，计算其相邻空间的和。如果和为8，则该空间被“1”包围。然后，您可以随机将其中一个“1”替换为“0”（假设您不需要固定数量的“1”和“0”）。 - Mel

这是错误的，如果多个0被1包围怎么办？ - rjv

实际上，我刚想到了一个解决方案来解决所示的例子。需要更清晰地定义封闭区域。一个由四个正交的“1”和四个对角线的“0”组成的“0”是否被认为是封闭的？ - Mel

不是很清楚你想实现什么。是例子中的输入还是期望的输出？你可以完整地提供一个包含示例输入和期望输出（以及可能的输出解释）的示例吗？ - skyking

@Woody1193 但是有一个被八个“1”包围的“0”，似乎不符合您指定的要求。而且还有被包围的“1”。我认为您应该改进您的问题。 - skyking

Answer 1

这段代码是否适合您？
基本上我是从左到右，从上到下填充矩阵。
当我需要向单元格分配0或1时，我会检查（北和西）是否添加1可以包围0；在这种情况下，我放置一个0，否则随机放置0或1。

import sys, random

n = int(sys.argv[1])
m = int(sys.argv[2])

# fill matrix with zeroes
matrix = [[0 for _ in xrange(m)] for _ in xrange(n)]

# functions to get north, south, west and east
# cell wrt this cell.
# If we are going out of bounds, we suppose the matrix
# is sorrounded by 1s.

def get_n(r, c):
    if r <= 0: return 1
    return matrix[r - 1][c]

def get_s(r, c):
    if r >= n - 1: return 1
    return matrix[r + 1][c]

def get_w(r, c):
    if c <= 0: return 1
    return matrix[r][c - 1]

def get_e(r, c):
    if c >= m - 1: return 1
    return matrix[r][c + 1]

# Checks if the cell is already enclosed by 3 1s.  
def enclosed(r, c):
    enclosing = get_n(r, c) + get_s(r, c) + get_w(r, c) + get_e(r, c)
    if (enclosing > 3): raise Exception('Got a 0 enclosed by 1s')
    return enclosing == 3

for r in xrange(n):
    for c in xrange(m):
        # check west and north
        if enclosed(r, c - 1) or enclosed(r - 1, c):
            matrix[r][c] = 0
        else:
            matrix[r][c] = random.randint(0, 1)

        print str(matrix[r][c]) + ' ',

    print ''

Sample run: python spaces.py 10 10

- affo

---

接近了，但不完全正确。如果您看看我的示例，您会注意到封闭还包括数组的边缘。因此，如果一组0在3个侧面被封闭，第四个侧面是数组的边缘，那么它仍然被视为被封闭。 - Woody1193

我的代码考虑了这个事实。这就是为什么我认为矩阵被1包围。你尝试执行代码，结果遇到了这个问题？ - affo

我现在注意到你编辑了你的问题并且“扩大”了“封闭”的定义。现在你想要避免被1包围的0的正方形。 - affo

你的解决方案不可行，因为它可能会生成一个包含3个或更多封闭点的块： (第1行) 10001 (第2行) 11111 - Anton Zuenko

是的，现在我知道了。之前的问题有点不同。我将在几个小时内提供一个新的解决方案。先要做一些事情。 - affo

@affo 是的，抱歉。我没有表达得像我想要的那样清楚。外壳可以是任意大小或形状。 - Woody1193

Answer 2

所以你可以做以下事情：

1. 用零填充数组
2. 随机选择一个点
3. 如果符合条件，则翻转颜色
4. 从第2步重复或退出

条件适用于全零数组。它在任何迭代中都成立。因此，通过归纳法，它对于最终数组也是正确的。

在第4步中，您可以通过执行N=a*b*1000次迭代或使红/黑比率接近1来决定是否停止或继续。在两种情况下，结果都会略有偏差，因为您从全零开始。

那么，什么是条件？您必须确保所有黑点相连，所有红点也相连。换句话说，最多有2个相连的集群。翻转颜色可能会创建更多的连接集群，因此仅在其数量为一或两个时翻转。您可以使用Union-Find算法非常高效地进行检查，在此处描述。

编辑：但是，如果您希望允许黑色点被红色点包围而不是反之，则可以更改条件以具有任意数量的黑色集群，但只有0或1个红色集群。

- Anton Zuenko

Answer 3

这是一种可能的检查条件的方式：

def: findStart(myArr):
    for i in range(len(myArr)):
        for j in range(len(myArr[0])):
            if(myArr[i][j] == 0):
                return (i,j)

def: checkCon(myArr, number_Ones):
    width = len(myArr[0])
    height = len(myArr)
    pen = []                      #A list of all points that are waiting to get a visit
    vis = []                      #A list of all points that are already visited
    x = findStart(myArr)

    while(len(pen) != 0):         #Visit points as long as there are points left
        p = pen.pop()             #Pick a point to visit

        if p in vis:
           #do nothing since this point already was visited

        else:
            vis.append(p)
            x,y = p

            #A vertical check
            if(x == 0 and myArr[x+1][y] == 0):
                pen.append((x+1,y))
            elif(x == (height-1) and myArr[x-1][y] == 0):
                pen.append((x-1,y))

            else:
                if(myArr[x-1][y] == 0 and x-1 >= 0):
                    pen.append((x-1,y))
                if(myArr[x+1][y] == 0):
                    pen.append((x+1,y))


            #A horizontal check    
            if(y == 0 and myArr[x][y+1] == 0):
                pen.append((x,y+1))
            elif(y == (width-1) and myArr[x][y-1] == 0):
                pen.append((x,y-1))

            else:
                if(myArr[x][y+1] == 0):
                    pen.append((x,y+1))
                if(myArr[x][y-1] == 0 and y-1 >= 0):
                    pen.append((x,y-1))                 


    print((height*width-number_Ones) == len(vis))       #if true, alle Zeros are connected and not enclosed

为了澄清，这只是一个检查条件的概念。想法是访问所有相连的零，并查看是否有任何未连接的零。如果是这种情况，则存在一些被包围的零。
当1形成类似以下矩阵框架时，此方法也无法工作：

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

再次强调，这只是一个概念 :)

- Robert K.

Answer 4

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

请注意，我已经定义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

- Woody1193