找到所有类似的“触摸” 2D数组中的元素(Python) [英] Locate all similar "touching" elements in a 2D Array (Python)
问题描述
让我们说我有一个数组:
Let's say I have the array:
someArray = [["0","1","1","0"]
["0","1","0","1"]
["0","1","0","1"]
["0","1","1","0"]]
我想要指出数组中的一个元素,然后能够识别每个类似的触摸元素(触摸的含义是,如果将数组视为网格,则它们将通过一个或多个连接进行连接)。例如,在这种情况下,如果我选择someArray [0] [0],它将得到[1] [0],[2] [0]和[3] [0],因为所有这些元素都是 0,并且彼此接触。我只是指触摸NESW,而没有上述指示的组合。
I would like to point out one element in the array and then be able to identify every similar "touching" element (touching meaning if the array was viewed as a grid, they would be connected through one or more connections). For example, in this case, if I chose someArray[0][0], it would give me [1][0],[2][0] and [3][0], because all of those elements are "0", and are "touching" one another. I only mean touching NESW, without the combinations of said directions.
我需要做些什么才能开始研究?
What would I need to do to start working on this?
编辑:原来只是洪水填充。
This turned out to be simply "Flood Fill".
推荐答案
您可以考虑学习如何实现宽度优先搜索和深度优先搜索,以实现您的目标。以下示例显示了如何在一个功能中轻松处理这两种搜索策略。模块化方法应该使代码易于更改。
You might consider learning how to implement breadth-first searches and depth-first searches in order to accomplish your objective. The following example shows how both of these search strategies can be easily handled in one function. A modular approach should make the code simple to change.
#! /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()
这篇关于找到所有类似的“触摸” 2D数组中的元素(Python)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!