alle ähnlichen „berührend“ Elemente in einem 2D-Array (Python)

Question

Lassen Sie uns sagen, dass ich das Array haben:

someArray = [["0","1","1","0"] 
      ["0","1","0","1"] 
      ["0","1","0","1"] 
      ["0","1","1","0"]] 

Ich möchte ein Element in dem Array hinzuweisen und dann in der Lage alle ähnlich zu identifizieren "berührendes" Element (berührende Bedeutung, wenn das Array als Gitter betrachtet wurde, wären sie durch eine oder mehrere Verbindungen verbunden). Wenn ich in diesem Fall zum Beispiel ein Array [0] [0] wähle, würde es mir [1] [0], [2] [0] und [3] [0] geben, weil alle diese Elemente " 0 "und" berühren "sich gegenseitig. Ich meine nur, NESW zu berühren, ohne die Kombinationen dieser Richtungen.

Was müsste ich tun, um damit zu arbeiten?

EDIT: Dies stellte sich als einfach "Flut füllen".

Answer 1

Sie könnten lernen, wie Sie breadth-first searches und depth-first searches implementieren, um Ihr Ziel zu erreichen. Das folgende Beispiel zeigt, wie beide Suchstrategien in einer Funktion einfach gehandhabt werden können. Ein modularer Ansatz sollte den Code einfach änderbar machen.

#! /usr/bin/env python3 
from collections import deque 
from operator import eq 


def main(): 
    """Show how to search for similar neighbors in a 2D array structure.""" 
    some_array = ((0, 1, 1, 0), 
        (0, 1, 0, 1), 
        (0, 1, 0, 1), 
        (0, 1, 1, 0)) 
    neighbors = (-1, 0), (0, +1), (+1, 0), (0, -1) 
    start = 0, 0 
    similar = eq 
    print(list(find_similar(some_array, neighbors, start, similar, 'BFS'))) 


def find_similar(array, neighbors, start, similar, mode): 
    """Run either a BFS or DFS algorithm based on criteria from arguments.""" 
    match = get_item(array, start) 
    block = {start} 
    visit = deque(block) 
    child = dict(BFS=deque.popleft, DFS=deque.pop)[mode] 
    while visit: 
     node = child(visit) 
     for offset in neighbors: 
      index = get_next(node, offset) 
      if index not in block: 
       block.add(index) 
       if is_valid(array, index): 
        value = get_item(array, index) 
        if similar(value, match): 
         visit.append(index) 
     yield node 


def get_item(array, index): 
    """Access the data structure based on the given position information.""" 
    row, column = index 
    return array[row][column] 


def get_next(node, offset): 
    """Find the next location based on an offset from the current location.""" 
    row, column = node 
    row_offset, column_offset = offset 
    return row + row_offset, column + column_offset 


def is_valid(array, index): 
    """Verify that the index is in range of the data structure's contents.""" 
    row, column = index 
    return 0 <= row < len(array) and 0 <= column < len(array[row]) 


if __name__ == '__main__': 
    main()