本文共 418 字，大约阅读时间需要 1 分钟。

Bessie需要用最少的行和列来消灭所有的 asteroid。这个问题可以建模为一个二分图匹配问题，其中左边的顶点代表行，右边的顶点代表列。每个 asteroid 连接对应的行和列。通过求解最大匹配数，可以得到最小的顶点覆盖数，即最少的行和列数量。

为了实现这一点，我们可以使用匈牙利算法来求解二分图的最大匹配。首先，建立一个二分图，其中左边的顶点是行，右边的顶点是列。每个 asteroid 连接它所在的行和列。然后，运行匈牙利算法，找到最大的匹配数。这个数即为最小的顶点覆盖数，也就是Bessie需要最少射击的次数。

具体来说，顶点编号从0开始，行数为0到N-1，列数从N到N+500-1。每个 asteroid 会在对应的行和列之间建立一条边。匈牙利算法会找到最大的匹配数，从而确定最小的行和列的数量。

通过这种方法，我们可以高效地解决这个问题，并找到最优的射击次数。

最终，Bessie需要的最少射击次数等于二分图的最大匹配数。

转载地址：http://yfxfk.baihongyu.com/