第四届蓝桥杯决赛B组C/C++——格子刷油漆

标题:格子刷油漆

X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如图1所示)

图1

现需要把这些格子刷上保护漆。你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)比如:a d b c e f 就是合格的刷漆顺序。c e f d a b 是另一种合适的方案。当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。

输入数据为一个正整数(不大于1000)

输出数据为一个正整数。

例如:

用户输入:

2

程序应该输出:

24

用户输入:

3

程序应该输出:

96

用户输入:

22

程序应该输出:

359635897

暴力搜索法:

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int book[2][10001];//标记格子是否走过 
int move[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};//格子移动的方向 
int n,sum = 0,count = 0;//n列,sum种方法,目前走了cou个格子 
void dfs(int i,int j,int count)
{
	if(count == 2*n)//当所有的格子都走了一遍了 
	{
		sum = (sum + 1) % MOD;//方法数+1 
		return;//回溯 
	}
	for(int k = 0;k < 8;k++)
	{
		int newi = i + move[k][0];
		int newj = j + move[k][1];
		if(!book[newi][newj] && newi < 2 && newi >= 0 && newj >= 0 && newj < n)
		{
			book[newi][newj] = 1;
			dfs(newi,newj,count + 1);
			book[newi][newj] = 0;//因为回溯了,所以将上一步走过的点重置为没走过 
		}
	}
	return;
}
int main()
{ 
	cin>>n;//输入列 
	//遍历枚举所有起始点 
	for(int i = 0;i < 2;i++) 
	{
		for(int j = 0;j < n;j++)
		{
			memset(book,0,sizeof(book));//将所有格子重置为没走过 
			book[i][j] = 1;//从当前点开始,所以当前点标记为走过 
			dfs(i,j,1);
		}
	}
	cout<<sum % MOD;
	return 0;
}

搜索并不难,但是会超时,我试过输入22,结果1分钟都没有出结果

后来在网上看到大家用的都是动态规划的方法,学习了个一知半解,主要是递推式太难推了,强烈吐槽这题,根本就是数学归纳法或者统计法,附上链接大家自己看吧

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据处理

ECC非对称加密算法

1.1K40
来自专栏数据之美

相似文档查找算法之 simHash 简介及其 java 实现

传统的 hash 算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。产生的两个签名,如果相等,说明原始内容在一定概 率 下是相...

969100
来自专栏鸿的学习笔记

写给开发者的机器学习指南(七)

Classifying email as spam or ham (NaiveBayes)

13110
来自专栏生信技能树

比较不同的对单细胞转录组数据normalization方法

使用CPM去除文库大小影响 之所以需要normalization,就是因为测序的各个细胞样品的总量不一样,所以测序数据量不一样,就是文库大小不同,这个因素是肯定...

86270
来自专栏AI科技大本营的专栏

没练过这个项目,怎么做AI工程师?

从年初起,几家国际大厂的开发者大会,无论是微软Build、Facebook F8还是稍后的Google I/O,莫不把“AI优先”的大旗扯上云霄。

10310
来自专栏WOLFRAM

用 Mathematica 生成正多面体链环

36170
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(十)No.77

大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet 大数据计数原理1+0=1这你都不会算(二)No.50 ...

209100
来自专栏CDA数据分析师

工具 | R语言数据可视化之数据分布图(直方图、密度曲线、箱线图、等高线、2D密度图)

数据分布图简介 绘制基本直方图 基于分组的直方图 绘制密度曲线 绘制基本箱线图 往箱线图添加槽口和均值 绘制2D等高线 绘制2D密度图 数据分布图简介 中医上讲...

455100
来自专栏祁旭翔的专栏

【 SPA 大赛】win10 python3.5.X 下开启 lightgbm 支持

GBDT (Gradient Boosting Decision Tree) 是机器学习中一个长盛不衰的模型,其主要思想是利用弱分类器(决策树)迭代训练以得到最...

3.3K00
来自专栏北京马哥教育

Numpy 隐含的四大陷阱,千万别掉进去了!

看起来效果不错。假设我们要对数据进行筛选,取第 1 列的第 1 行和第 3 行数据构成一个 2 x 1 的列向量。先看对 array 的做法:

27720

扫码关注云+社区

领取腾讯云代金券