gpt4 book ai didi

algorithm - 找到覆盖二进制矩阵的最小矩形集

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:12:19 24 4
gpt4 key购买 nike

<分区>

假设我有以下二进制矩阵:

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

我想找到一组平行于 x 轴和 y 轴的矩形,它们覆盖每个 1 至少一次并且不覆盖单个 0 具有最小基数(最少数量的矩形)。在上面的示例中,这将是矩形 ((0, 3), (6, 5))((3, 0), (5, 8)) (符号的形式为 (topleft, bottomright))- 最小的解决方案是使用两个矩形。

我之前的尝试是找到面积最大且仅覆盖 1 的矩形,将该矩形添加到集合中,然后将所有这些 1 标记为 0,直到所有 1 都消失。虽然这个集合会覆盖每个 1 而不是单个 0,但它不一定具有最小基数(该算法在上面的示例中会失败)。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com