检查矩阵元素是否连续

Question

我想解决这个问题好几天了，但一直没能解决。在

我需要检查矩阵中的元素是否连续。例如：

1 0 1 0 0 0
0 1 0 0 1 0
0 0 1 1 0 0

在这种情况下，1是连接的，因为它们是连续的。在

检查此示例：

^{pr2}$

在这种情况下，1不是连续的，因为它们没有连接。 如您所见，矩阵大小不同。在

Answer 1

一点递归就可以了。在

以下是对算法的描述：

1. 找到一个1
2. 将其标记为0
3. 移动到所有相邻单元格
4. 在所有相邻的a 1单元格中，从第2点开始重复。在
5. 当无处可去时，再找一个1如果找到了，那么矩阵就不连通了

为了澄清最后一点-如果矩阵中还有剩余的1，这意味着我们的算法没有到达它。由于它只移动到相邻的单元，所以我们得出结论，剩下的1没有连接到步骤1中的初始1。在

代码如下：

def find_a_1():
    for row_i, row in enumerate(matrix):
        if '1' in row:
            return {
                'row': row_i,
                'col': row.index('1'),
            }

def walk_the_matrix(point):
    """ Clear current point and move to adjacent cells that are "1s" """
    # check if this is a valid cell to work on:
    try:
        if point['row'] < 0 or point['col'] < 0:
            raise IndexError  # prevent negative indexes
        if matrix[point['row']][point['col']] == '0':
            return  # nothing to do here, terminate this recursion branch
    except IndexError:
        return  # we're outside of the matrix, terminate this recursion branch
    # clear this cell:
    matrix[point['row']][point['col']] = '0'
    # recurse to all 8 directions:
    for i in (-1, 0, 1):
        for j in (-1, 0, 1):
            if (i, j) == (0, 0):
                continue
            walk_the_matrix({
                'row': point['row'] + i,
                'col': point['col'] + j,
            });

示例：

^{pr2}$

请注意，这会使matrix列表发生变异。在

Answer 2

因为我误读了原始问题而编辑了

问题似乎可以归结为“有没有完全被0包围的1？”。在

计算每个细胞周围的细胞数的一个简单方法是使用2D卷积，假设{}由0和1组成

import numpy as np
import scipy.signal as ss

kernel = np.ones((3,3))

count = ss.convolve2d(my_array, kernel, mode='same') # Count number of 1s around each cell
contig = my_array * count # Remove counts where the 'centre cell' is zero

要检查my_array是否有任何独立的1，只需检查contig中是否有任何1：

^{pr2}$