在矩阵中查找组大小

Question

所以我想知道，有没有一种简单的方法可以检测矩阵中相邻相同值的大小？例如，当查看下面 0 到 12 之间的值矩阵时： [0,4] 处的组大小为 14，因为有 14 个 5 相互连接。但是1和4没有连接。

Answer 1

我认为你可以使用呼吸优先搜索（好吧，尝试将矩阵想象成一棵树）

这是一个伪 python 实现。这样做。这对你有用吗？你有没有考虑到复杂性？

代码

visited_nodes = set()

def find_adjacent_vals(target_val, cell_row, cell_column):
    if inside_matrix(cell_row, cell_column)
        cell = matrix(cell_row, cell_column)
        if cell not in visited_nodes:
            visited_nodes.add(cell)
            if cell.value == target_val:
                return (1 + 
                        find_adjacent_vals(target_val, cell_row + 1, cell_column) # below
                        +find_adjacent_vals(target_val, cell_row - 1, cell_column) # above
                        +find_adjacent_vals(target_val, cell_row, cell_column -1) # left
                        +find_adjacent_vals(target_val, cell_row, cell_column +1) # right
                        ))

print "Adjacent values count: " + str(find_adjacent_vals(target_val, target_row, target_column))

说明

假设您从一个节点开始，您开始分支出之前未访问过的访问节点。你这样做直到你没有遇到相同值的新单元格。由于设置逻辑，每个节点保证只有 1 个父节点。因此没有细胞被重复计算。