c - 仅包含 0 或 1 的二维数组

Question

我有一个二维数组，其中随机包含 0 或 1 的值。

如何(最有效地)确定值 1 的最低元素(最大行迭代 i)和最右边元素(最高列迭代 j)？

例如:

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

我的程序应该回答i = 3(假设第一行是i = 0)和j = 2(假设第一行列为 0 )。

Answer 1

这是一个想法:

1. 从最底行开始，使用 memrchr 查找每行中的最后一个 1(我有点假设您将数字存储为 char 又名 8 位整数)。
2. 最终您会找到包含 1 的行。这是您对i 的回答。我们使用缓存友好的一次一行操作走到了这一步，因为 C 使用行优先顺序。
3. 在上面，您现在还知道了 j 的下限(因为您在最后一行中找到了包含任何 1 的最后一个 1 s)。
4. 对于其余行，从超过 j 下限到每行末尾的行使用 memrchr。如果您在那里发现任何 1，请更新下限。重复此操作，直到检查完所有行。
5. 当然，如果您在最后一列中发现 1，您可以立即停止。