python - 确定矩阵的所有元素是否在Python中连接

Question

注意:不要提及用于创建矩阵的 Numpy，因为我不能使用那个特定的库。

我一直在研究一个 Python 程序，该程序检查板内的所有元素(板尺寸可以改变)是否已连接。例如，这个板的元素都是连接的:

board = [
    [1, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
]

但是，我目前的程序是错误的，因为某些特定情况会返回相反的 bool 值。我应该怎么做？

这是我目前的代码:

#Should return False, returns False
board1 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 0, 1]
    ]

#Should return True, returns False
board2 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 1, 0]
    ]

#Should return True, returns True
board3 = [
    [0, 1, 0],
    [1, 1, 1],
    [0, 1, 0]
    ]

#Should return True, returns False
board4 = [
    [0, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    ]
def check(board):
    adjacent_total = []

    for x in range(len(board)):
        for y in range(len(board[0])):
            adjacent = []

            if board[x][y] == 1:

                for i in range (x-1, x+2):
                    for j in range (y-1, y+2):
                        if i == x and j == y:
                            continue
                        if i == len(board) or j == len(board[0]):
                            break

                        if i >= 0 and j >= 0:
                            if board[i][j] == 1:
                                adjacent.append((i,j))

            else:
                adjacent = None
            adjacent_total.append(adjacent)

    for i in adjacent_total:

        if i is None:
            continue
        elif len(i) == 1:
            return False
    return True

print(check(board1))
print(check(board2))
print(check(board3))
print(check(board4))

Answer 1

关于:

import itertools
#Should return False, returns False
board1 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 0, 1]
]

#Should return True, returns False
board2 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 1, 0]
]

#Should return True, returns True
board3 = [
    [1, 0, 1],
    [1, 1, 1],
    [0, 1, 0]
]

#Should return True, returns False
board4 = [
    [1, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
]

class Matrix(object):
    def __init__(self, m):
        self.m = m

    @property
    def numrows(self): return len(self.m)

    @property
    def numcols(self): return len(self.m[0])

    def get(self, r, c):
        return self.m[r][c]

    def set(self, r, c, v):
        self.m[r][c] = v

    def is_valid(self, r, c):
        return (0 <= r < self.numrows) and (0 <= c < self.numcols)

    def neighbors(self, r, c):
        #offsets =
        #    (0,1), (0,-1), (1,0), (-1,0),
        #    (-1,-1), (-1,1), (1,-1), (1,1),
        #]
        offsets = itertools.product([-1,0,1],[-1,0,1])
        neighbors = []
        for (dr,dc) in offsets:
            if (dr,dc) == (0,0): continue
            rr = r + dr
            cc = c + dc
            if self.is_valid(rr, cc): neighbors.append((rr,cc))
        return neighbors

    def find_nonzero(self):
        for (r,c) in self.iter():
            if self.get(r,c) == 1: return (r,c)
        return None

    def iter(self):
        return itertools.product(xrange(self.numrows), xrange(self.numcols))

    def show(self):
        for row in self.m: print(row)


def grow(m, r, c):
    m.set(r, c, 0)
    for (rr,cc) in m.neighbors(r, c):
        if m.get(rr,cc): grow(m, rr, cc)


def check(board):
    m = Matrix(board)

    # Find any non-zero element
    (r,c) = m.find_nonzero()
    print("Found non-zero element at ({},{})".format(r,c))

    # Call grow, a recursive function that "unsets" the neighbors of (r,c) and recurses
    grow(m, r, c)

    m.show()

    # Check if any are still set
    return (m.find_nonzero() is None)    

用法:

for i,board in enumerate([board1, board2, board3, board4]):
    print("Checking board %d:" % (i+1))
    res = check(board)
    print(res)
    print('---')

输出(删除了 m.show() 的结果板):

Checking board 1:
Found non-zero element at (0,0)
False
---
Checking board 2:
Found non-zero element at (0,0)
True
---
Checking board 3:
Found non-zero element at (0,0)
True
---
Checking board 4:
Found non-zero element at (0,0)
True
---

我创建了一个Matrix 类，它抽象了很多工作。从那里，我创建了一个 grow 函数，它接受一个 Matrix 和一个(行，列)索引。 grow 函数“取消设置”(row, col) 处的值并递归所有设置的邻居。

结果是一个矩阵，其中来自第一个非零元素的所有“连接”元素都设置为零。

然后，如果矩阵还剩下任何非零元素，则它们没有连接，check 返回 False。