MENU

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

April 21, 2018 • Read: 248 • 算法

格子刷油漆

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

现需要把这些格子刷上保护漆。你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)比如: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 分钟都没有出结果

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

最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code