gpt4 book ai didi

查找覆盖二维数组中某些元素的最小矩形数的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:26:08 25 4
gpt4 key购买 nike

<分区>

简化后,我要解决以下问题:

您有一个由 0 和 1 填充的二维数组。找到最小数量的矩形,使它们覆盖所有 1。矩形不应重叠。

函数签名可能如下所示: List<Rectangle> FindCoveringRectangles(bool[,] array)

我已经有了一个“足够好”的解决方案,但并不总能找到最少数量的矩形。我想知道是否有一些众所周知的高效算法可以用来解决这个问题?

例子:

输入数组:

..........
.1.....11.
.......11.
...111....
...111....
...111....
....1111..
....1111..
......11..
..........

(为了便于阅读,用点代替了 0)

可能会产生以下矩形:

(2,2,2,2),
(2,8,3,9),
(4,4,6,6),
(7,5,8,8),
(9,7,9,8)

(上、左、下、右),基于 1

可以有不止一种解决方案,但一个就足够了。

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