Определить, связаны ли все элементы матрицы в 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 и индекс (строка, столбец). Функция роста «unsets» значение в (row, col) и рекурсирует на всех установленных соседях.

В результате получается матрица, в которой все «подключенные» элементы от первого ненулевого элемента равны нулю.

Тогда, если в матрице остались ненулевые элементы, они не были связаны, а check возвращает False.