"Matrix" 宽度不等 - 循环的有效方式

Question

尝试实现路径查找算法，该算法在矩阵中查找相邻的 True 值并将它们连接成一条路径。并寻找矩阵中的所有独立路径。元素只有 1s 或 0s

示例：

matrix = [
    [1, 0, 1, 0],
    [1, 1, 0, 0],
    [1, 0, 1, 1]
]

第一条路径：[(0,0), (1,0), (1,1), (2,0)]

第二条路径：[(0,2)]

第三条路径：[(2,2), (2,3)]

现在，这很简单，但我想知道如何有效地遍历宽度不等的矩阵。

示例：

matrix = [
    [1, 0, 1, 0],
    [1, 1, 0, 0],
    [1, 0, 1, 1],
    [1, 0, 0],
    [0, 1]
    [1, 0, 1, 0, 1, 1]
]

我在想两个办法：

Check the number of element in a row and skip it if end is reached. Using if and cols[row] where cols represent the number of elements in each column and row is the current row: cols = [len(row) for row in matrix]

Populate "the missing" elements with 0s to get row * column matrix

虽然这些方法可能适用于相对较小的矩阵，但问题会出现在大数字上，例如

如果任何行有 50k 个元素而所有其他行有大约 1k 个元素，那么 n 行需要填充 49k 次（第二种方法）。使用第一个，在最坏的情况下（0s 和 1s 交替出现）检查将发生 49k/2 次（因为每个 1 都是一个新路径和算法将寻找相邻的）。

我想知道是否有更有效的方法，检查尽可能少的“空白点”或根本不检查它们。

Answer 1

在一般情况下，您可以像这样遍历行和列而无需明确提及列宽。

for row in matrix:
    for value in row:
        ...

对于您要解决的这个特定问题，可能仍然需要记录上一行的长度：

last_row = None
last_row_len = 0
for row in matrix:
    for idx, value in enumerate(row):
        if idx >= last_row_len:
            ...
        elif value and last_row[idx]:
            ...
    last_row = row
    last_row_len = len(row)

Python 中更有效的解决方案可以使用 itertools.groupby 将 0 和 1 分组到每一行的块中。你可以自己想办法实现。

"Matrix" 宽度不等 - 循环的有效方式

"Matrix" of unequal width - efficient way to loop over

python

algorithm

matrix

path-finding