找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

【算法漫画】展览规划

admin 2019-12-15 14:38 349人围观 C++相关













对于题目的第一小题我们可以发现,因为我们希望不重不漏地参观完所有房间,那么对于每个房间我们都需要开一扇门来进入(此处我们把从该房间离开进入下一个房间所开的门归给下个房间),那么我们需要开16扇门来参观这16个房间,而最后我们还是在最后参观的那个房间之中的,但是题目要求的是我们要离开房间,那么只要对现在的次数再加上1,作为从第四行离开房间的代价即可,对于题目的第二小题,我们从题目中可以获得信息,我们需要从第一行中的一个房间进入,从最后一行的一个房间离开,而这中间的每次移动我们只能移动向上下左右中还没有被遍历过的房间,我们考虑对其进行二分图染色,将相邻的格子染成黑白两种不同的颜色,而整个路程就是一个黑白交替的序列,分析这个序列的性质我们可以发现,如果序列的第一项与最后一项相同,那么序列的长度一定是奇数,不能够满足经过16个房间的要求,那么序列的第一项必定和最后一项的颜色和相反,因为题目的数据范围很小,我们考虑用暴力方法对其策略正确性进行检验,我们固定第一行的一个房间作为起点,也就是整个序列的第一项,然后与其相对应的我们可以在最后一行中找到两个与其颜色不同的格子,我们很容易可以找出方案路线使其合法。综上分析,我们也就得到了答案,总方案数有8种,方案合法条件便为对方格图进行二分图染色,所选的起点和终点颜色不同即为合法方案。
解析作者:Johnson_Wu


▼往期精彩回顾▼【算法漫画】谜题毒酒【算法漫画】夜过吊桥【算法漫画】超级蛋测试【算法漫画】击落战舰【算法漫画】鸡块数字
【算法漫画】煎饼翻转
【算法漫画】科学家在世的最好时代【算法漫画】斐波那契的兔子问题中国机长-了不起的中国机长卷纸秘密-一卷纸到底有多长?痛定思痛-高以翔事件给我们的警示我要减肥-马思纯何时能瘦成图三?一晚不倒-小姐姐为何摇一晚上不会倒?童年回忆-数学建模教你如何玩转贪吃蛇
版权声明:本篇漫画版权归校苑数模公众号所有,任何形式的转载及内容使用需与校苑数模工作人员模小数联系,未经授权的转载与使用我们将对其追究法律责任。合作与转载请在公众号会话窗口回复【合作】或【转载】。感谢您的支持与认可。


看都看完了,还不点这里试试


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:校苑数模,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......