確定矩陣中的所有元素是否都以Python連接

Question

注意：不要提及用於矩陣創建的Numpy，因爲我無法使用該特定庫。

我一直在研究一個Python程序，它檢查一個電路板內的所有元件（電路板尺寸是否可以改變）是否連接在一起。例如，該電路板的元件都被連接：

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

然而，當前的程序我有故障時，如某些特定情況下返回相反布爾值。我應該做些什麼呢？

這是當前代碼我有：

#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和（行，列）索引。增長函數「取消」設置（row，col）的值並在所有設置的鄰居上遞歸。

結果是一個矩陣，其中來自第一個非零元素的所有「連接」元素都設置爲零。

然後，如果矩陣還有任何非零元素，則它們沒有連接，並且check返回False。