gpt4 book ai didi

algorithm - 一个图形中最多可以放置多少张多米诺骨牌

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

假设方格纸上有一些图形。人物的两边在方格纸的线条上笔直。图可以有任何(甚至不是凸的)形状。如何找到可以放置在该图中的多米诺骨牌(1x2 矩形)的最大数量。不允许将多米诺骨牌放在另一个上面。只有当它的边正好落在方格纸的线上时,才允许以这种方式放置多米诺骨牌。

最佳答案

看起来像 maximum cardinality matching problem in a bipartite graph .正方形是顶点,多米诺骨牌是属于匹配的边。

要查看该图是二分图,请想象正方形是用棋盘绘制的。黑色的只与白色相邻,反之亦然。

关于algorithm - 一个图形中最多可以放置多少张多米诺骨牌,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4780201/

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