java - 迭代减少到空矩阵

Question

这就是问题所在:我得到了一个类似这样的矩阵

输入:

1 1 1
1 1 1
1 1 1

在每一步中，我都需要找到一个由 1 和 0 组成的“第二”矩阵，并且同一行或同一列上没有两个 1。然后，我将从原始矩阵中减去第二个矩阵。我将重复这个过程，直到我得到一个全为 0 的矩阵。此外，我需要采取尽可能少的步骤。

我需要在 O(n) 时间内打印所有“秒”矩阵。在上面的例子中，我可以通过依次减去这三个矩阵来分 3 步得到空矩阵:

预期输出:

1 0 0
0 1 0
0 0 1

0 0 1
1 0 0
0 1 0

0 1 0
0 0 1
1 0 0

我编写了一个尝试，其中我正在寻找第一个最大值并根据该值的索引创建第二个矩阵。但是对于上面的输入我得到了 4 个输出矩阵，这是错误的:

我的输出:

1 0 0 
0 1 0 
0 0 1 

0 1 0 
1 0 0 
0 0 0 

0 0 1 
0 0 0 
1 0 0 

0 0 0 
0 0 1 
0 1 0  

我的解决方案适用于大多数测试用例，但不适用于上面给出的测试用例。有人可以给我一些关于如何进行的指示，或者找到一个保证最优性的算法吗？

有效的测试用例:

输入:

0 2 1
0 0 0
3 0 0

输出

0 1 0
0 0 0
1 0 0

0 1 0
0 0 0
1 0 0 

0 0 1
0 0 0
1 0 0

Answer 1

对每一行/列求和并取其中的最大值，即可获得减少为空矩阵所需的最佳矩阵减法次数。

---

例如:

1 2 4 0 = 7
2 2 0 1 = 5
0 0 1 0 = 1
3 0 2 1 = 6
= = = =
6 4 7 2

这意味着这个矩阵需要 7 次最优减法才能清空。

---

我相信从这个开始倒数并从具有该值的列/行中删除将解决您的问题(我不确定选择这些的有效方法 - 蛮力？)。
您还可以使用之前的方法删除多余的元素。

---

例如(使用上面的矩阵)。

第七步:
我们必须从第 1 行和第 3 列中减去。

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

解决了这个问题，所以现在我们可以使用您以前的方法删除“bonus”元素。

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

现在再次应用每行/列的总和并继续下一步。

第 6 步:

1 2 3 0 = 6
1 2 0 1 = 4
0 0 1 0 = 1
3 0 2 0 = 5
= = = =
5 4 6 1

下一个减法:

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

等等。

---

注意:对于“全为 1”的矩阵，这仍然不能很好地工作，因为您会遇到从每一行和每一列中选择 1 的问题(与您在示例中所做的相同)。

但有人可以扩展我的解决方案。