【2013年第四届蓝桥杯C/C++程序设计本科B组决赛 格子刷油漆(编程大题) 】_楚江枫的博客-程序员宝宝

技术标签: BFS+DFS  蓝桥  

2013年蓝桥杯C/C++ B组 决赛试题

格子刷油漆
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如图1所示),现需要把这些格子刷上保护漆。
你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)
比如:a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。
输入数据为一个正整数(不大于1000)
输出数据为一个正整数。

例如:
用户输入:
2
程序应该输出:
24
再例如:
用户输入:
3
程序应该输出:
96
再例如:
用户输入:
22
程序应该输出:
359635897
资源约定:
峰值内存消耗 < 64M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。

1)暴力,只能过一些很小的数据 QAQ

2)正解应是 DP

代码:

#include<cstdio>
#include<cstring>
using namespace std;
int num,vis[2][1010],x[8] = {
   0,0,-1,1,-1,1,-1,1},y[8] ={-1,1,0,0,-1,-1,1,1};
void dfs(int a,int b,int cut,int n){
    if(cut == 2 * n){
        num++;return ;
    }
    for(int i = 0; i < 8; i++){
        int fx = x[i] + a,fy = y[i] + b;
        if(fx < 0 || fy < 0 || fx >= 2 || fy >= n || vis[fx][fy])
            continue;
        vis[fx][fy] = 1;
        dfs(fx,fy,cut + 1,n);
        vis[fx][fy] = 0;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    num = 0;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < n; j++)
            memset(vis,0,sizeof(vis)),vis[i][j] = 1,dfs(i,j,1,n);
    printf("%d\n",num);
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/WYK1823376647/article/details/72674073

智能推荐

ncnn源码分析1_一名小菜鸟的学习之路的博客-程序员宝宝_ncnn源码分析

&nbsp; &nbsp; &nbsp; &nbsp; 前段时间,分别尝试了使用腾讯开源的深度学习推理框架ncnn、陈天奇大神团队开源的tvm,及最新的阿里开源mnn,就好用程度来说,腾讯的n...

跟着鸟哥学Linux系列笔记1_weixin_30448603的博客-程序员宝宝

跟着鸟哥学Linux系列笔记0-扫盲之概念跟着鸟哥学Linux系列笔记0-如何解决问题装完linux之后,接下来一步就是进行相关命令的学习了第五章:首次登录与在线求助man page1. X Window切换至命令行模式:  Ctrl + Alt + F1~F6: 文字界面登录 tty1~tty6终端;  Ctrl + Alt + F7: 图形界面桌面2. ...

2.5.3 创建子弹;2.5.4创建子弹Prefab;2.5.5发射子弹;2.6 创建敌人;2.7.1 添加碰撞体_taotaoahui的博客-程序员宝宝

using UnityEngine;using System.Collections;//[AddComponentMenu("MyGame/Rocket")]public class Rocket : MonoBehaviour { // 子弹飞行速度 public float m_speed = 10; // 生存事件 public float m

我读 《国富论》 - 亚当 · 斯密 / 论增进劳动生产力的因素,以及劳动生产物在各个阶层中自然分配的顺序_简简单单OnlineZuozuo的博客-程序员宝宝

文章目录我读 《国富论》 - 亚当 · 斯密 / 论增进劳动生产力的因素,以及劳动生产物在各个阶层中自然分配的顺序1、论工资2、国家工资3、对婚姻影响我读 《国富论》 - 亚当 · 斯密 / 论增进劳动生产力的因素,以及劳动生产物在各个阶层中自然分配的顺序1、论工资分工引发的各种改良会促使劳动生产力提高,劳动工资也会随之增长。可是所有的生产物品却呈现越来越廉价的趋势,原因就在于,他们所需要付出的劳动少了。各种商品是在劳动等量的情况下进行彼此交换的。无论在哪里, 对劳动者的普通工资起决定作用的都是

互联网日报 | 理想汽车登陆纳斯达克;苏宁易购会员数量突破6亿;高德地图上线“司机公厕”..._liudada8265的博客-程序员宝宝

今日看点✦理想汽车正式在纳斯达克挂牌上市,股价开盘大涨35%✦ 苏宁易购上半年实现营收1182.43亿元,会员数量突破6亿✦ 高德地图上线北京92处可临时停车公厕,车辆可临停15分钟✦...

SCI投稿前需要准备哪些材料?_EA-ISET学术的博客-程序员宝宝

今天EA-ISET协会给大家分享一篇关于SCI投稿知识的文章。好不容易写好文章,看准了一个杂志,撸起袖子准备投稿时,突然发现除了需要上传初稿附件外,必须上传一些其他附件,以及要求论文中必须在参考文献前附上一些利益等声明条款;比如:★常见附件材料:Cover Letter, Highlights, Reviewer suggestions,Checklist,Graphic Abstract等;★常见附在参考文献前的声明条款:Availability of data and material;

随便推点

Android进阶之路①:五大布局_老天子的博客-程序员宝宝

Android进阶之路①:五大布局Android进阶之路①:五大布局LinearLayout 线性布局常用属性视图RelativeLayout常用属性视图TableLayout常用属性视图FramLayout视图AbsoluteLayout常用属性视图本文总结Android界面之:Android五大布局LinearLayou...

flashback database 方法_congxinlan3332的博客-程序员宝宝

SQL*Plus: Release 10.2.0.4.0 - Production on Sat Jan 23 23:30:17 2010Copyright (c) 1982, 2007, Oracle. All...

mozjpeg:JPEG图片压缩5%,获Facebook支持_weixin_33889665的博客-程序员宝宝

mozjpeg是一个来自Mozilla实验室的JPEG图像编码器项目,目标是在不降低图像质量且兼容主流的解码器的情况下,提供产品级的JPEG格式编码器来提高压缩率以减小JPEG文件的大小。Mozilla指出,这些年来,网站的图片使用数量和大小都在与日俱增,而HTML、JS和CSS文件大小都相对减小了。也就是说在页面加载的过程中,图片占用了大量的网络流量...

uboot-2015-07的start.S的文件启动过程_shenlong1356的博客-程序员宝宝

https://blog.csdn.net/u013904227/article/details/51648179https://www.cnblogs.com/debruyne/p/9208809.htmlhttps://blog.csdn.net/weixin_41734376/article/details/98586549

数据结构之通用树结构的实现_顾小豆的博客-程序员宝宝_树结构实现

之前我们讲了树的定义和操作,这节我们讲一下如何实现这些操作。既然要考虑如何实现,那就得说说树的存储结构。大家都知道树是非线性数据结构,显然我们无法用数组来表示树的逻辑结构。那我们应该怎么办呢?通过什么来表示呢?其实可以设计结构体数组对结点间的关系进行表述。如下图所示:从上图发现,将根结点的双亲定义为-1,表示其没有双亲;将根的孩子结点的双亲定义为0,表示其双亲是根结点;将根结点孩子1的孩子结点的双...