第四届蓝桥杯决赛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分钟都没有出结果
后来在网上看到大家用的都是动态规划的方法，学习了个一知半解，主要是递推式太难推了，强烈吐槽这题，根本就是数学归纳法或者统计法，附上链接大家自己看吧
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读