algorithm - 从二进制矩阵中划掉坏线

Question

给定边为 n 的二元方阵。
我们会将至少包含一个 0 的任何行或列视为“坏”。
任务是取消所有坏行和坏列。
任务需要使用 O(1) 的额外内存。

1 1 0     0 0 0
1 1 1  => 1 0 0
1 0 1     0 0 0

困难的是，我们不能在遍历过程中发现不良行时将其无效(否则我们将始终以零矩阵结束)。所以我正在寻找这样的数据结构或数据表示方式，以便它可以在算法遍历矩阵时存储有关坏行和坏列的所有信息。

Answer 1

实际上我们只需要 2n 位就可以得到答案:我们需要知道每一行和每一列是好 (1) 还是坏 (0)。每个单元格中的答案将是行和列答案的乘积。

让我们将大部分信息存储在矩阵本身中:我们可以使用第一行来保留所有列的记录(0 或 1)，但首先，第一列保留所有行的记录，但第一行，我们还需要两位来保留第一行和第一列的记录。

首先我们得到这两个额外的位(检查第一行和第一列)。

然后查找并存储其他行和列的记录。

然后计算除第一行和第一列之外的所有矩阵中的结果位。

最后:如果第一行不好，则应将其作废，否则应保持原样，对第一列也应这样做。