NC51272 棋盘覆盖

棋盘覆盖

https://ac.nowcoder.com/acm/problem/51272

题目:

给出一张n×n(n≤100) 的国际象棋棋盘,其中被删除了一些点,问可以使用多少1*2的多米
诺骨牌进行掩盖。

题解:

在这里插入图片描述
先进行黑白染色,相邻的两个黑白就是一个骨牌,又因为一个格子不能放多个骨牌,所以相当于找每个格子的搭档(搭档即为相邻的点),使得搭档的数量足够多
在这里插入图片描述
裸的二分图最大匹配

代码:

全部评论

相关推荐

12-13 14:51
已编辑
井冈山大学 算法工程师
龙虾x:算法比你强的没有你美,比你美的…..算了已经没有比你美的了
工作两年想退休了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务