如何解决这个矩阵问题以收集所有种子？
How to solve this matrix problem to collect all the seeds?
问题描述：
仓鼠哈米发现了一栋有种子的建筑。帮他把它们都收集起来。
建筑呈房间矩阵排列，部分房间内有种子。一旦进入建筑物，Hammy 只会 运行 在一条直线上，一直穿过建筑物并收集那条直线上的所有种子。建筑物有多个入口，Hammy可以随意进入任意行或任意列。
他想用尽可能少的运行收集建筑物中所有的种子。
这是建筑物的示例布局：
+---+---+---+---+---+
| * | | * | | |
+---+---+---+---+---+
| * | * | | | |
+---+---+---+---+---+
| * | | | | * |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
该建筑有 25 个房间（5X5），但只有 8 rooms 个有种子（包含“*”的房间）。
我们需要找到最小的 运行s 来收集所有的种子。
我的做法：
我试着用一些 Greedy Approach 来解决它，这里是：
1) Start with row/column that contains maximum rooms of seeds (For example: column 1 for here).
2) Updating rows/columns (no of rooms that contain seeds).
3) Repeating steps 1 & 2 until all the seeds are collected.
所以，对于这个例子，当我应用我的方法时，
以Column 1开头（包含3个房间），
更新后，接下来是Column 4、
这是现在的建筑情况，
+--+---+---+--+---+
| | | * | | |
+--+---+---+--+---+
| | * | | | |
+--+---+---+--+---+
| | | | | * |
+--+---+---+--+---+
| | | | | |
+--+---+---+--+---+
| | | | | |
+--+---+---+--+---+
现在三个房间都有种子，都在不同的rows或columns上，我需要把它们全部拿走，结果我用完了5 runs，也就是maximum（获取所有行或所有列始终是根本不考虑种子的答案）。无需任何计算，任何人都可以到达这里。包含所有行或列的运行。
但是这个问题可以在4 运行秒内解决。
我正在寻找一个 approach/algorithm 来找到最小的 运行s（我需要 运行 的行 and/or 列）。
也许另一种方法是集中精力减少 rows/columns 剩余种子的数量。
您可以像这样计算每个 row/column 中的种子数来找到 rows/columns。
3 1 1 2 1
+---+---+---+---+---+
| * | | * | | | 2
+---+---+---+---+---+
| * | * | | | | 2
+---+---+---+---+---+
| * | | | | * | 2
+---+---+---+---+---+
| | | | * | | 1
+---+---+---+---+---+
| | | | * | | 1
+---+---+---+---+---+
然后你把连续有种子的行的总和除以种子的数量。这将为您提供此列的分数。像这样对所有行和列执行此操作。
例如，第 1 行与第 1 列和第 3 列共享种子。
第 1 列有 3 个种子，第 3 列有 1 个，即 4 个种子。
将此数字除以行数得到 2，因此第 1 行的分数为 2。
2 2 2 1 2
+---+---+---+---+---+
| * | | * | | | 2
+---+---+---+---+---+
| * | * | | | | 2
+---+---+---+---+---+
| * | | | | * | 2
+---+---+---+---+---+
| | | | * | | 2
+---+---+---+---+---+
| | | | * | | 2
+---+---+---+---+---+
然后你取 row/column 的最小数字不为零。
通过这样做，它会得出第 4 列（释放两行，得分 1）。
↓
+---+---+---+---+---+
| * | | * | | |
+---+---+---+---+---+
| * | * | | | |
+---+---+---+---+---+
| * | | | | * |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
然后是第 1 行、第 2 行（每行释放 1 列，得分 2）和第 3 行（释放 2 列，得分 1），顺序不限。
+---+---+---+---+---+
| * | | * | | | ←
+---+---+---+---+---+
| * | * | | | | ←
+---+---+---+---+---+
| * | | | | * | ←
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
我不知道这种方法是否适用于一般情况。
这个问题基本上是二分图中的顶点覆盖。图中的一组节点对应于行。另一组对应于列。边对应种子，其中每条边的端点对应边对应种子的坐标。
来自 Kőnig's theorem, the size of a minimum cover is equal to the size of a maximum matching, which can be computed efficiently using Hopcroft–Karp。
要在每个 运行 之前划一行，您基本上可以检查：
- 如果我们丢弃当前的一条线，将清除多少条相反（正交）线：+1 for each
- 剩下多少条平行线给运行：每条-1。
第一名的得分运行：
-4 -4 -4 (-2) -4
+---+---+---+---+---+
| * | | * | | | -3
+---+---+---+---+---+
| * | * | | | | -3
+---+---+---+---+---+
| * | | | | * | -3
+---+---+---+---+---+
| | | | * | | -4
+---+---+---+---+---+
| | | | * | | -4
+---+---+---+---+---+
- 第 1 列将清除 0 行并将其他 4 列留给 运行 = -4
- 第 4 列将清除 2 行并将其他 4 列留给 运行 = -2
- 第 1 行将清除 1 列并将其他 4 行留给 运行 = -3
第二个分数运行：
-3 -3 -3 -4 -3
+---+---+---+---+---+
| * | | * | | | (-1)
+---+---+---+---+---+
| * | * | | | | (-1)
+---+---+---+---+---+
| * | | | | * | (-1)
+---+---+---+---+---+
| | | | | | -3
+---+---+---+---+---+
| | | | | | -3
+---+---+---+---+---+
可以使用动态规划在多项式时间 (cols*rows) 中求解（计算每行和列的第一个分数，然后在消耗一行时仅更新受影响的分数）。
矩阵可以构成一个二分图，所有的行可以构成左边的顶点和右边的所有列。如果一个单元格中有种子，它将在左右之间建立一条边。因此，给定的示例将形成以下二分图。
现在我们只需要 select 一组顶点，这样每条边的至少一个端点将包含在该顶点集中。在图论中，这被称为顶点覆盖问题。 https://en.wikipedia.org/wiki/Vertex_cover
为了实现最小顶点覆盖，我们需要找到图的最大匹配。 Hopcroft–Karp algorithm provides us to find a maximum matching in polynomial time (in worst case O(n^2.5). Once we have a maximum matching, Kőnig's theorem 帮助我们在 O(n^2) 时间内找到最小顶点覆盖。
工作原理：
说M是最大匹配，初始设置为空。
从二分图中，我们需要找到最大的顶点不相交的最短增广路径集 P.
这里 P = {r1c1, r2c2, r3c5, r4c4}
M = M（对称差分）P = {r1c1, r2c2, r3c5, r4c4}
在这个例子中，没有更多的增广路径了。这样就达到了最大匹配。
现在使用 Kőnig 定理，我们需要从匹配的 M 中找到最小顶点覆盖。
这里顶点覆盖将是 {r1, r2, r3, c4}
So the minimum run is 4.
此过程的总体复杂度为 O(E * (V^0.5))，E 和 v 是边和顶点集的长度。对于稀疏矩阵，它将在近线性时间内 运行。
另一个例子：
+---+---+---+---+---+
| | * | * | | * |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
| * | * | | * | |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
二分图：
最大匹配 M = {r1c2, r2c4, r3c1}
最小顶点覆盖 = {r1, r3, c4}
So the minimum run is 3.
如果你只对最小值感兴趣运行（只看数字，不需要显示细节）那么你不需要实现Kőnig定理，因为最大匹配的大小是最小顶点覆盖集的长度。
问题描述：
仓鼠哈米发现了一栋有种子的建筑。帮他把它们都收集起来。
建筑呈房间矩阵排列，部分房间内有种子。一旦进入建筑物，Hammy 只会 运行 在一条直线上，一直穿过建筑物并收集那条直线上的所有种子。建筑物有多个入口，Hammy可以随意进入任意行或任意列。
他想用尽可能少的运行收集建筑物中所有的种子。
这是建筑物的示例布局：
+---+---+---+---+---+
| * | | * | | |
+---+---+---+---+---+
| * | * | | | |
+---+---+---+---+---+
| * | | | | * |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
该建筑有 25 个房间（5X5），但只有 8 rooms 个有种子（包含“*”的房间）。
我们需要找到最小的 运行s 来收集所有的种子。
我的做法：
我试着用一些 Greedy Approach 来解决它，这里是：
1) Start with row/column that contains maximum rooms of seeds (For example: column 1 for here).
2) Updating rows/columns (no of rooms that contain seeds).
3) Repeating steps 1 & 2 until all the seeds are collected.
所以，对于这个例子，当我应用我的方法时，
以Column 1开头（包含3个房间），
更新后，接下来是Column 4、
这是现在的建筑情况，
+--+---+---+--+---+
| | | * | | |
+--+---+---+--+---+
| | * | | | |
+--+---+---+--+---+
| | | | | * |
+--+---+---+--+---+
| | | | | |
+--+---+---+--+---+
| | | | | |
+--+---+---+--+---+
现在三个房间都有种子，都在不同的rows或columns上，我需要把它们全部拿走，结果我用完了5 runs，也就是maximum（获取所有行或所有列始终是根本不考虑种子的答案）。无需任何计算，任何人都可以到达这里。包含所有行或列的运行。
但是这个问题可以在4 运行秒内解决。
我正在寻找一个 approach/algorithm 来找到最小的 运行s（我需要 运行 的行 and/or 列）。
也许另一种方法是集中精力减少 rows/columns 剩余种子的数量。 您可以像这样计算每个 row/column 中的种子数来找到 rows/columns。
3 1 1 2 1
+---+---+---+---+---+
| * | | * | | | 2
+---+---+---+---+---+
| * | * | | | | 2
+---+---+---+---+---+
| * | | | | * | 2
+---+---+---+---+---+
| | | | * | | 1
+---+---+---+---+---+
| | | | * | | 1
+---+---+---+---+---+
然后你把连续有种子的行的总和除以种子的数量。这将为您提供此列的分数。像这样对所有行和列执行此操作。
例如，第 1 行与第 1 列和第 3 列共享种子。 第 1 列有 3 个种子，第 3 列有 1 个，即 4 个种子。 将此数字除以行数得到 2，因此第 1 行的分数为 2。
2 2 2 1 2
+---+---+---+---+---+
| * | | * | | | 2
+---+---+---+---+---+
| * | * | | | | 2
+---+---+---+---+---+
| * | | | | * | 2
+---+---+---+---+---+
| | | | * | | 2
+---+---+---+---+---+
| | | | * | | 2
+---+---+---+---+---+
然后你取 row/column 的最小数字不为零。 通过这样做，它会得出第 4 列（释放两行，得分 1）。
↓
+---+---+---+---+---+
| * | | * | | |
+---+---+---+---+---+
| * | * | | | |
+---+---+---+---+---+
| * | | | | * |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
然后是第 1 行、第 2 行（每行释放 1 列，得分 2）和第 3 行（释放 2 列，得分 1），顺序不限。
+---+---+---+---+---+
| * | | * | | | ←
+---+---+---+---+---+
| * | * | | | | ←
+---+---+---+---+---+
| * | | | | * | ←
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
我不知道这种方法是否适用于一般情况。
这个问题基本上是二分图中的顶点覆盖。图中的一组节点对应于行。另一组对应于列。边对应种子，其中每条边的端点对应边对应种子的坐标。
来自 Kőnig's theorem, the size of a minimum cover is equal to the size of a maximum matching, which can be computed efficiently using Hopcroft–Karp。
要在每个 运行 之前划一行，您基本上可以检查：
- 如果我们丢弃当前的一条线，将清除多少条相反（正交）线：+1 for each
- 剩下多少条平行线给运行：每条-1。
第一名的得分运行：
-4 -4 -4 (-2) -4
+---+---+---+---+---+
| * | | * | | | -3
+---+---+---+---+---+
| * | * | | | | -3
+---+---+---+---+---+
| * | | | | * | -3
+---+---+---+---+---+
| | | | * | | -4
+---+---+---+---+---+
| | | | * | | -4
+---+---+---+---+---+
- 第 1 列将清除 0 行并将其他 4 列留给 运行 = -4
- 第 4 列将清除 2 行并将其他 4 列留给 运行 = -2
- 第 1 行将清除 1 列并将其他 4 行留给 运行 = -3
第二个分数运行：
-3 -3 -3 -4 -3
+---+---+---+---+---+
| * | | * | | | (-1)
+---+---+---+---+---+
| * | * | | | | (-1)
+---+---+---+---+---+
| * | | | | * | (-1)
+---+---+---+---+---+
| | | | | | -3
+---+---+---+---+---+
| | | | | | -3
+---+---+---+---+---+
可以使用动态规划在多项式时间 (cols*rows) 中求解（计算每行和列的第一个分数，然后在消耗一行时仅更新受影响的分数）。
矩阵可以构成一个二分图，所有的行可以构成左边的顶点和右边的所有列。如果一个单元格中有种子，它将在左右之间建立一条边。因此，给定的示例将形成以下二分图。
现在我们只需要 select 一组顶点，这样每条边的至少一个端点将包含在该顶点集中。在图论中，这被称为顶点覆盖问题。 https://en.wikipedia.org/wiki/Vertex_cover
为了实现最小顶点覆盖，我们需要找到图的最大匹配。 Hopcroft–Karp algorithm provides us to find a maximum matching in polynomial time (in worst case O(n^2.5). Once we have a maximum matching, Kőnig's theorem 帮助我们在 O(n^2) 时间内找到最小顶点覆盖。
工作原理：
说M是最大匹配，初始设置为空。
从二分图中，我们需要找到最大的顶点不相交的最短增广路径集 P.
这里 P = {r1c1, r2c2, r3c5, r4c4}
M = M（对称差分）P = {r1c1, r2c2, r3c5, r4c4}
在这个例子中，没有更多的增广路径了。这样就达到了最大匹配。
现在使用 Kőnig 定理，我们需要从匹配的 M 中找到最小顶点覆盖。
这里顶点覆盖将是 {r1, r2, r3, c4}
So the minimum run is 4.
此过程的总体复杂度为 O(E * (V^0.5))，E 和 v 是边和顶点集的长度。对于稀疏矩阵，它将在近线性时间内 运行。
另一个例子：
+---+---+---+---+---+
| | * | * | | * |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
| * | * | | * | |
+---+---+---+---+---+
| | | | * | |
+---+---+---+---+---+
二分图：
最大匹配 M = {r1c2, r2c4, r3c1}
最小顶点覆盖 = {r1, r3, c4}
So the minimum run is 3.
如果你只对最小值感兴趣运行（只看数字，不需要显示细节）那么你不需要实现Kőnig定理，因为最大匹配的大小是最小顶点覆盖集的长度。