分布式服务 nhibernate GMU vue实现原理 bootstrap框架 jq选择第一个子元素 鼠标进入和离开事件 hadoop组件 oracle时间格式化 cmd清空命令 wps文件修复工具下载 python中的def java新建文件 java获取 linux入门基础 javascript源代码 linux格式化命令 如何给黑白照片上色 显示器面板类型 js文件上传 超过响应缓冲区限制 php随机数 lol无法连接服务器 摇骰子表情包 微信群群发软件 debian安装教程 求字符串长度的函数 护魂者的命运 dos常用命令 excel指数函数 磁盘碎片整理 magicexif 华为手机内部存储清理 ps名片制作教程 正则表达式语法大全 高通骁龙430测评 小猴子怎么画 php源代码 ps怎么设计艺术字 换肤软件
当前位置: 首页 > 学习教程  > 编程语言

2016年第七届蓝桥杯C/C++B组省赛题目7:剪邮票

2021/2/13 18:31:19 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述: 如 , 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来,要求必须是连着的。 (仅仅连接一个角不算相连) 比如, , 中,粉红色所示部分就是合格的剪取。 请你计算,一…

题目描述:

【图1.jpg】
, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】
【图3.jpg
中,粉红色所示部分就是合格的剪取。

请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

题目答案:

116

题目思路:
i1、i2、i3、i4和i5为枚举要剪下的5个数,对这五个数构成的连通性进行dfs判断,
如果dfs后测得从i1出发从上下左右四个方向上深度优先搜索遍历为i2~i5之间的所有点,
cnt标记i5能够走到的是i1~i5这些点的个数,如果cnt == 5就说明是连在一起的,
注意从4和8向右行走走不到5和9,并且从5和9出发向左行走走不到4和8~
所以遇到index == 4或者index == 8并且是向右走的时候continue~(index == 5和9并向左走同理~)
将result加一~累加得到的result就是结果116~

代码:

#include <iostream>
using namespace std;
int dis[4] = {1, -1, 4, -4};//移动方向
int visit[13];//标记所经历的点
int i1, i2, i3, i4, i5, cnt, result = 0;
void dfs(int index) {
    visit[index] = 1;//标记所经历的点
    if (cnt >= 5) return;
    for (int i = 0; i < 4; i++) {
        if ((dis[i] == 1 && (index == 4 || index == 8)) || (dis[i] == -1 && (index == 5 || index == 9)))
            continue;
        int t = index + dis[i];//移动到下一个点
        if (t >= 1 && t <= 12 && visit[t] == 0 && (t == i2 || t == i3 || t == i4 || t == i5))
        {
            cnt++;
            dfs(t);
        }
    }
}
int main() {
    for (i1 = 1; i1 <= 12 - 4; i1++) {
        for (i2 = i1 + 1; i2 <= 12 - 3; i2++) {
            for (i3 = i2 + 1; i3 <= 12 - 2; i3++) {
                for (i4 = i3 + 1; i4 <= 12 - 1; i4++) {
                    for (i5 = i4 + 1; i5 <= 12; i5++) {
                        memset(visit, 0, sizeof(visit));
                        cnt = 1;
                        dfs(i1);
                        if (cnt == 5) result++;
                    }
                }
            }
        }
    }
    cout << result;
    return 0;
}

转自链接:https://blog.csdn.net/liuchuo/article/details/69569281


本文链接: http://www.dtmao.cc/news_show_700262.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?