Find enclosed spaces in array

Question

So, I'm generating an array of spaces, which have the property that they can be either red or black. However, I want to prevent red from being enclosed by black. I have some examples to show exactly what I mean:

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

If red is 0 and black is 1, then this example contains four enclosures, all of which I want to avoid when I generate the array. The inputs I have are the size of the array and the number of 1s I can generate.

How would I go about doing this?

Answer 1

Does this code fits well for you?
Basically I fill a matrix from left to right, from top to bottom.
When I have to assign 0 or 1 to a cell, I check (north and west) if adding a 1 could enclose a 0; in this case I put a 0, else a random 0 or 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

Answer 2

So you can do the following:

1. Fill array with zeroes
2. Randomly select a point
3. If the condition holds, flip color
4. Repeat from step 2 or exit

The condition holds for all-zeros array. It is hold on any iteration. So, by induction, it is also true for the final array.

In the step 4 you can decide whether to stop or continue by doing, say N=a*b*1000 iterations or whether the ratio red/black is close to 1. In both cases, the result would be slightly biased since you start from all zeros.

Now, what is the condition. You have to ensure that all black points connected and all red points connected as well. In other words, there's maximum 2 connected clusters. Flipping a color could create more connected clusters, so you flip only when the its number is one or two. You can do the check quite efficiently using Union-Find algorithm, described here.

Edit: if however you want to permit black points to be surrounded by red ones but not vice-versa, you may change the condition to have any number of black clusters but only 0 or 1 of red clusters.