Ustal, czy wszystkie elementy macierzy są połączone w Pythonie

Question

Uwaga: Nie wspominaj o Numpy dla tworzenia macierzy, ponieważ nie mogę użyć tej konkretnej biblioteki.

Pracuję nad programem w języku Python, który sprawdza, czy wszystkie elementy wewnątrz tablicy (rozmiar tablicy może się zmienić) są połączone. Na przykład, elementy tego forum są wszystkie podłączone:

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

Jednak obecny program mam jest wadliwy, ponieważ niektóre szczególne przypadki powrotu przeciwną wartość logiczną. Co powinienem robić zamiast tego?

To jest bieżący kod mam:

#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

Co o:

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)  

Zastosowanie:

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

wyjścia (z wynikającymi płyt z m.show() usunięte):

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 
--- 

Tworzę klasę Matrix, która znacznie upraszcza pracę. Stamtąd tworzę funkcję grow, która akceptuje indeks Matrix i (wiersz, kolumnę). Funkcja grow "zeruje" wartość w (wiersz, col) i rekurenci na wszystkich ustawionych sąsiadach.

Wynikiem jest macierz, w której wszystkie "połączone" elementy z pierwszego niezerowego elementu są ustawione na zero.

Następnie, jeśli macierz ma pozostały niezerowe elementy, nie zostały połączone, a check zwraca False.